1495번

1495번 - 기타리스트

처음에는 트리 구조로 생기기 때문에 BFS를 쓸까 하다가... 제한을 보고 이건 답도 없겠다 싶어서 DP를 생각했다.

하지만... 이것도 내 스스로 못 풀고 결국 점화식을 보고야 말았다...

1차 점화식으로는 절대 연관관계가 나올 수 없을 거라고 생각하고 2차식을 그렇게 고민했는데...

항상 점화식은 생각하는 것보다 간단하게 나온다는 점..

D[N][V] = N번째 곡을 V로 연주할 수 있는가? 있으면 1 없으면 0

이 문제에서 배울점

=> DP 문제를 풀 때 항상 어떤 경우의 수, 즉 값을 찾아야 한다는 고정관념이 어느정도 문제를 풀다 보니까 생겼다.

     하지만 이 문제와 같은 경우에는 존재여부만을 캐시에 저장해서 푼다는 점.

     최적화 문제를 결정문제로 바꿔서 푸는 DP문제도 있다는 점을 잘 캐치!

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int D[101][1001];
 
int N, S, M;
vector<int> V;
int go(int n, int v)
{
    if (v > M || v < 0)
    {
        return 0;
    }
 
    if (n == 0)
    {
        if (v == S)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
 
    if (D[n][v] >= 0)
    {
        return D[n][v];
    }
 
    D[n][v] = go(n - 1, v - V[n - 1]) || go(n - 1, v + V[n - 1]);
 
    return D[n][v];
 
 
}
int main()
{
    scanf("%d %d %d", &N, &S, &M);
    V.resize(N);
    memset(D, -1, sizeof(D));
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &V[i]);
    }
 
    bool ch = true;
    for (int i = M; i >= 0; i--)
    {
        if (go(N, i)==1)
        {
            ch = false;
            printf("%d\n", i);
            break;
        }
    }
    if (ch)
    {
        printf("-1\n");
    }
    
 
    return 0;
}