[BOJ] 5557 : 1학년 - travelbeeee

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

---

[알고리즘풀이]

DP 문제로 다음과 같이 배열을 정의하면 된다.

Dp[i][j] : i번 째 수까지 이용해서 j 를 만들 수 있는 경우의 수.

그럼, 다음과 같은 점화식이 성립합니다.

Dp[i][j] = Dp[i - 1][j + N[i]] + Dp[i - 1][j - N[i]]

i번 째 수까지 이용해서 j를 만드는 경우의 수는

(i - 1)번 째 수까지 이용해서 (j + N[i])를 만든 경우의 수에 N[i] 를 빼는 경우와

(j - N[i])를 만든 경우의 수에 N[i]를 더하는 경우로 나눠서 생각할 수 있다.

#include<iostream>

using namespace std;

long long dp[100][21];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	long long n, N[100];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> N[i];
	
	dp[0][N[0]] = 1;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 0; j <= 20; j++) {
			if (0 <= j + N[i] && j + N[i] <= 20)
				dp[i][j] += dp[i - 1][j + N[i]];
			if (0 <= j - N[i] && j - N[i] <= 20) 
				dp[i][j] += dp[i - 1][j - N[i]];
		}
	}
	cout << dp[n - 2][N[n - 1]];
}

---