본문 바로가기

알고리즘 관련/BOJ

BOJ)12869 뮤탈리스크

문제:icpc.me/12869


3개의 SCV의 체력이 주어질 때 뮤탈리스크가 각 SCV를 서로 다른 공격으로 공격할 때 공격횟수의 최솟값을 출력하는 문제이다.


이 문제는 그리디하게 힘들다고 생각한 순간 동적 계획법을 떠올릴 수 있다.


하지만 공격횟수로 테이블을 잡기 애매하기 때문에 각 SCV의 체력에 포커스를 맞춘다면 


dp[x][y][z] = 체력이 x , y ,z 인 SCV를 파괴하는데 필요한 최소 공격 횟수로 테이블을 세울 수 있고


점화식은 공격가능한 6가지 방법 중에 최솟값을 호출하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int dp[66][66][66];
int n, a, b, c;
int func(int x, int y, int z) {
    if (!x&&!y&&!z)return 0;
    int &ret = dp[x][y][z];
    if (ret != -1)return ret;
    ret = INF;
    ret = min(ret, func(max(0, x - 9), max(0, y - 3), max(0, z - 1)) + 1);
    ret = min(ret, func(max(0, x - 9), max(0, y - 1), max(0, z - 3)) + 1);
    ret = min(ret, func(max(0, x - 3), max(0, y - 9), max(0, z - 1)) + 1);
    ret = min(ret, func(max(0, x - 1), max(0, y - 9), max(0, z - 3)) + 1);
    ret = min(ret, func(max(0, x - 3), max(0, y - 1), max(0, z - 9)) + 1);
    ret = min(ret, func(max(0, x - 1), max(0, y - 3), max(0, z - 9)) + 1);
    return ret;
}
int main() {
    memset(dp, -1sizeof(dp));
    scanf("%d"&n);
    scanf("%d%d%d"&a, &b, &c);
    printf("%d\n", func(a, b, c));
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13309 트리  (1) 2017.06.21
BOJ)2507 공주 구하기  (0) 2017.06.18
BOJ)12922 블럭 퍼즐  (0) 2017.06.15
BOJ)12963 달리기  (0) 2017.06.15
BOJ)8217 유성  (1) 2017.06.14