백준 12869번 : 뮤탈리스크 (C++)
2021. 8. 11. 21:44
https://www.acmicpc.net/problem/12869
12869번: 뮤탈리스크
1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다.
www.acmicpc.net
코드
|
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
28
29
30
|
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int scv[3];
int dp[66][66][66];
int func(int s,int c,int v)
{
if(s==0 && c==0 && v==0)
return 0;
if(dp[s][c][v]!=-1)return dp[s][c][v];
dp[s][c][v]=1000000000;
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-9),max(0,c-3),max(0,v-1))+1);
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-9),max(0,c-1),max(0,v-3))+1);
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-3),max(0,c-9),max(0,v-1))+1);
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-3),max(0,c-1),max(0,v-9))+1);
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-1),max(0,c-9),max(0,v-3))+1);
dp[s][c][v]=min(dp[s][c][v],func(max(0,s-1),max(0,c-3),max(0,v-9))+1);
return dp[s][c][v];
}
int main() {
memset(dp,-1,sizeof(dp));
cin>>n;
for(int i=0;i<n;i++)
cin>>scv[i];
cout<<func(scv[0],scv[1],scv[2]);
return 0;
}
|
cs |
풀이
dp배열을 이용해서 중복된 경우에 연산하지 않고 바로 횟수를 알수있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 6679번 : 싱기한 네자리 숫자 (C++) (0) | 2021.08.09 |
|---|---|
| 백준 16197번 : 두 동전 (C++) (0) | 2021.07.22 |
| 백준 14225번 : 부분수열의 합 (C++) (0) | 2021.07.21 |
| 백준 14888번 : 연산자 끼워넣기 (C++) (0) | 2021.07.20 |
| 백준 1339번 : 단어 수학 (C++) (0) | 2021.07.09 |
