[BOJ/C++] 5557(1학년)

1. Link

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

• 0이상 20이하인데 1이상으로 두고 풀어서 시간 괜히 잡아먹은 문제. 문제 슥 읽고 대충 넘어가는 습관을 자제하자.
• DP 문제라는 것을 알게 되는 순간 쉬워지는 문제입니다. 문제를 보고 빠르게 유형을 파악하도록 노력합시다.

2. 풀이 과정

1. '+' 또는 '-'를 넣어 등식을 만든다 -> 백트래킹, DP
2. 주어진 숫자 갯수 n의 조건이 100까지라면, 2^100은 당연하게 시간초과일 것임 -> DP

• 처음에는 백트래킹으로 0보다 낮아지거나 20보다 높아지면 return하는 함수를 만드려고 했으나, 2^100은 생각보다 훨씬 오래 걸리고 의도와 많이 벗어나 있음을 파악했습니다. 따라서 다양한 가짓수를 적재적소에 더할 수 있는 동적 프로그래밍 알고리즘을 사용하여 구현했습니다.

  점화식은 조건에 따라 다음과 같이 작성하였습니다.

  (i는 n만큼의 갯수, j는 0부터 20까지의 범위)

  1. dp[i][j] += dp[i - 1]j + a[i]] -> 이전 값(j)에서 a[i]를 더했을 때의 가짓수를 전달합니다.
  2. dp[i][j] += dp[i - 1]j - a[i]] -> 이전 값(j)에서 a[i]를 뺐을 때의 가짓수를 전달합니다.

3. 정답 코드

#include<iostream>
using namespace std;
#define ll long long

int n, answer;
int a[101];
ll dp[101][21];

void input() {
	cin >> n;
	for (int i = 1; i < n; ++i) cin >> a[i];
	cin >> answer;
}

void solution() {
	input();
	dp[1][a[1]] = 1;
	for (int i = 2; i < n; ++i) {
		for (int j = 0; j <= 20; ++j) {
			if (j + a[i] <= 20) {
				dp[i][j] += dp[i - 1][j + a[i]];
			}
			if (j - a[i] >= 0) {
				dp[i][j] += dp[i - 1][j - a[i]];
			}
		}
	}
	cout << dp[n - 1][answer];
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}