Scoring Hack - 17234

//Scoring Hack
 
#include <iostream>
using namespace std;
 
int N, A, B;
bool cache[601][501][51];
 
void init()
{
    cin >> N >> A >> B;
    cache[0][0][0] = true;
}
 
bool dp(int score, int turn, int dturn)
{
    if(score < 0) return false;
    if(turn < 0) return false;
    if(dturn < 0) return false;
    return cache[score][turn][dturn];
}
 
int main()
{
    init();
    for(int i = 1; i<N+A; ++i)
        for(int j = 1; j<=N; ++j)
            for(int k = 0; 10*k<=j; ++k)
            {
                if(dp(i-A, j-1, k))
                    cache[i][j][k] = true;
                if(dp(i-B, j-1, k))
                    cache[i][j][k] = true;
                if(i%2 == 0)
                    if(dp(i/2, j-1, k-1))
                        cache[i][j][k] = true;
            }
    for(int turn = 0; turn<=N; ++turn)
        for(int dturn = 0; dturn*10 <= turn; ++dturn)
            for(int score = N; score<N+A; ++score)
                if(cache[score][turn][dturn])
                {
                    cout << turn;
                    return 0;
                }
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/17234

17234번: Scoring Hack

 

 

 

 

 

 

Scoring Hack

반복문을 사용한 dp를 이용해 해결했습니다.

C[score][turn][dturn] = if(C[score-A][turn-1][dturn]) true

                              if(C[score-B][turn-1][dturn]) true

                              if(C[score/2][turn-1][dturn-1]) true

즉, 이전에 가능한 상태들이 true일때, 현재 상태로도 올수 있기에 true로 변경해 주고

모든 가능한 범위에 대해 탐색이 끝난후에는 [N ...N+A) 구간에 대해  가장 turn이 작으면서 유효한 곳을 찾아 turn을 출력하면 됩니다.

 

(처음에는 greedy하게 해결할 수 있는줄 알았습니다.

즉 이전 가능한 상태들의 최소값들중 가장 작은값에 1을 더한것이 현재 상태로 올수있는 최소라고 생각했습니다. 하지만 다시 생각해보니 이전 상태에서의 최소는 *2를 하는과정을 최대한 당겨서 사용한 것이지만 뒤에있는 상태에선 *2를 최대한 아껴서 나중에 사용하는것이 더 최선의 답이 될수 있습니다. 따라서 greedy하게는 해결할 수 없다는 것을 알았습니다.

그 반례가 

500 1 1 입니다.)