백준 5557 - 1학년 (c++)

백준 5557 - 1학년

문제 링크

생각 및 접근

• 문제 입력을 먼저 분석했다.
  • 처음에 총 숫자의 갯수를 주고, 맨 마지막으로 주는 숫자는 플러스와 마이너스를 한 결과값, 나머지 중간에 있는 숫자는 피연산자들이다.
• dp[i][j]
  • i번째 피연산자를 플러스 또는 마이너스로 계산했을 때, 결과 j가 나오는 경우의 수를 저장한다.
• dp[i][j]의 초깃값
  • 첫 피연산자가 k라고 하면, 뺄수는 없으므로 dp[1][k] = 1이 된다.
  • 연산의 초깃값이 k가 되고, k가 될 수 있는 경우의 수가 하나밖에 존재하지 않는다.
• dp[i][j]의 탐색
  • dp[i - 1]를 순회하면서 피연산자 num를 더하거나 뺄 수 있는 후보를 찾는다. 후보를 찾았고, 그 후보에서 num을 더하거나 뺐을 때 0 이상 20 이하라면, dp[i][j + num] += dp[i - 1][j]; 혹은 dp[i][j - num] += dp[i - 1][j];를 한다.

    for (int i = 2; i <= n - 1; i++) {
      cin >> num;
      // dp[i - 1]에서 num을 더하거나 뺄 수 있는 후보 찾기
      for (int j = 0; j <= 20; j++) {
          // 후보를 찾았다.
          if (dp[i - 1][j] > 0) {
              // j에서 (후보의 연산 결과 값에서) num을 더하거나 뺐을 때 0이상 20이하라면 그 경우의 수를 더해준다.
              if (j + num <= 20)    dp[i][j + num] += dp[i - 1][j];
              if (j - num >= 0)     dp[i][j - num] += dp[i - 1][j];
          }
      }
    }

코드

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

int n, num;
long long dp[101][21];

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

    cin >> n >> num;
    dp[1][num] = 1;

    for (int i = 2; i <= n - 1; i++) {
        cin >> num;
        for (int j = 0; j <= 20; j++) {
            if (dp[i - 1][j] > 0) {
                if (j + num <= 20)    dp[i][j + num] += dp[i - 1][j];
                if (j - num >= 0)     dp[i][j - num] += dp[i - 1][j];
            }
        }
    }

    cin >> num;
    cout << dp[n - 1][num];
}

채점 결과