백준 1495 - 기타리스트 (c++)

백준 1495 - 기타리스트

문제 링크

생각 및 접근

• dp[i][j]

  • i번째 음악 볼륨 리스트에서 볼륨을 오르내릴 때, j 크기의 볼륨을 가질 수 있는가.
  • 가질 수 있다면 true, 가질 수 없다면 false.

• dp[i][j]의 초깃값

  • 아직 아무 음악을 탐색하지 않았으므로, 0번째 음악 리스트에는 초깃값 S 크기의 볼륨을 가질 수 있다.
  • 즉, dp[0][s] = true;

• dp[i][j] 탐색

  • i번째 음악 볼륨 리스트에서 볼륨을 오르내릴 때, dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다. 후보를 찾고, i번째 음악 볼륨을 오르내려서 범위 내에 있다면, dp[i][오르내린 볼륨 결과]를 true로 만들어준다.

    // 음악을 1번 음악부터 n번 음악까지 탐색한다.
    for (int i = 1; i <= n; i++) {
      // i번째 음악 볼륨을 입력 받는다.
      cin >> v;
    
      // j-for문 : dp[i - 1]를 탐색해서 볼륨을 오르내릴 후보를 찾는다.
      for (int j = 0; j <= m; j++) {
          // 볼륨을 오르내릴 후보를 찾았다
          if (dp[i - 1][j]) {
              if (j + v <= m) dp[i][j + v] = true;
              if (j - v >= 0) dp[i][j - v] = true;
          }
      }
    }

코드

#include <bits/stdc++.h>
using namespace std;

int n, s, m, v;
bool dp[101][1001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n >> s >> m;
    dp[0][s] = true;

    for (int i = 1; i <= n; i++) {
        cin >> v;
        for (int j = 0; j <= m; j++) {
            if (dp[i - 1][j]) {
                if (j + v <= m) dp[i][j + v] = true;
                if (j - v >= 0) dp[i][j - v] = true;
            }
        }
    }

    bool flag = false;
    for (int i = m; i >= 0; i--) {
        if (dp[n][i]) {
            cout << i;
            flag = true;
            break;
        }
    }
    if (!flag)   cout << -1;
}

채점 결과