[백준 1495] 기타리스트

www.acmicpc.net/problem/1495

1495번: 기타리스트

DP를 사용하는 문제이다. DP[I][J]를 가능한 최댓값으로 접근하면 문제를 풀 수 없다. 경우의 수가 많기 때문

따라서 DP[I][J]는 I번째 노래에서 J의 볼륨이 가능한지 여부여야 한다. 

DP[0][S] = 1로 초기화 된다. 

그 다음에 입력을 받으면서 이전 노래에서 J 볼륨이 가능했다면 J +- IDX가 가능한지 확인하여 DP 배열에 체크한다.

마지막 노래에 볼륨 조절이 불가하면 -1을 리턴하라고 했으므로 DP[N][J]의 값이 모두 0이면 -1을 리턴한다.

#include <stdio.h>

using namespace std;

int dp[101][1001];
int n, s, m;
int main(void)
{
  scanf("%d %d %d", &n, &s, &m);
  dp[0][s] = 1;
  for (int i = 1; i <= n; i++)
  {
    int idx;
    scanf("%d", &idx);
    for (int j = 0; j <= m; j++)
    {
      if (dp[i - 1][j] == 0)
      {
        continue;
      }

      if (j - idx >= 0)
      {
        dp[i][j - idx] = 1;
      }

      if (j + idx <= m)
      {
        dp[i][j + idx] = 1;
      }
    }
  }

  for (int i = m; i > -1; i--)
  {
    if (dp[n][i] == 1)
    {
      printf("%d\n", i);
      return 0;
    }
  }

  printf("-1\n");
  return 0;
}