zz12345의 코딩 공부

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배열을 이용해서 중복된 경우에 연산하지 않고 바로 횟수를 알수있다. 

공유하기

facebook twitter kakaoTalk kakaostory naver band