안녕하세요,
재재입니다.
boj 12869 뮤탈리스크 문제에 대한 솔루션입니다.
BOJ 12869 뮤탈리스크
(1) 문제 설명
분류 : dynamic programming
출처 : https://www.acmicpc.net/problem/12869
최대 3명의 scv가 주어지며, 뮤탈리스크 하나가 scv 를 공격한다.
첫번째로 공격 받는 scv 는 9의 체력을, 두번째는 3, 마지막으로 세번째는 1이 소모된다.
최소한의 공격으로 모든 scv 를 죽였을 때, 뮤탈리스크가 공격한 횟수의 최솟값을 출력하면 된다.
(2) 풀이 도출
전형적인 dynamic programming 문제로,
top down approach 혹은 bottom up 을 적용해도,
큰 무리 없이 해결 할 수 있습니다.
점화식은 다음과 같습니다.
dp[s1][s2][s3] : scv 의 체력이 s1, s2, s3 남았을 때,
모두 0으로 만드는데 소모되는 공격 횟수의 최소값
공격 받는 scv 의 순서만 정해주면 되는데 아래 처럼,
$$ 3! = 6 $$
총 6가지의 경우만 존재하기 때문에 직접 나열해도 큰 어려움이 없습니다.
(3) 정답 코드
BOJ 12869 뮤탈리스크