[ 백준 5557 ] 1학년 (C++)

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

5557번: 1학년

 

배낭 문제를 먼저 풀어서 그런지 쉽게 풀었다. 근데 신기한건 정말 내 생각대로 풀고 정답을 봤는데 내 코드랑 똑같았다. 나도 실력이 늘었나??^^

 

dp 문제니깐 dp 정의부터 하자!!

 

dp[i][j] = k

i번째 숫자까지의 조합으로 j를 만들 수 있는 경우의 수가 k 가지

 

dfs 또는 bfs랑 거의 흡사하다. 첫번째 숫자를 기준으로 +-(다음 숫자)를 해주고 범위가 0~20 사이면 경우의 수를 더해주면 된다. 

 

1. 우선 첫번째 숫자를 만드는 경우는 한가지 뿐이므로 대입해주고 시작한다. 처음 입력값은 num이라는 배열에 저장한다.

 

dp[1][num[1]] = 1;

 

2. i번째일때 모든 j에 대해 i-1번째 숫자를 넣을 수 있는지 검사한다. 

 

dp[i - 1][j] 가 true인 경우 숫자를 더하거나 뺄 수 있다는 뜻이다. 

1) 더하는 경우 
if (j + num[i] <= 20) true, 더할 수 있으므로 더해준다.
-- dp[i][j + num[i]] += dp[i - 1][j]

2) 빼는 경우
if (j - num[i] >= 0) true, 뺄 수 있으므로 빼준다.
-- dp[i][j - num[i]] += dp[i - 1][j];

 

마지막 정답은 dp[n - 1][num[n]] 를 출력해주면 된다. 왜냐하면 dp[n-1][num[n]] 은 n-1번째 숫자까지의 조합으로 num[n]을 만들 수 있는 경우의 수를 뜻하기 때문이다. 

 

만약에 배낭문제를 잘 이해했다면 어렵지 않게 풀 수 있는 문제라고 생각한다!

 

#include <iostream>
using namespace std;

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

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> num[i];

	dp[1][num[1]] = 1;

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

	cout << dp[n - 1][num[n]] << endl;

	return 0;
}