[백준 / C++] 5557번: 1학년 (다이나믹 프로그래밍, dp)

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

5557번: 1학년

 

난이도: solve.ac 골드 5

 

알고리즘 분류

다이나믹 프로그래밍 (dp)

 

접근 방법 및 구현

i - 1 번째 수까지 사이에 + 또는 - 집어넣어 계산한 결과가 j이고, 이를 만드는 경우의 수가 n개라고 해보자.

 

나는 이걸 이렇게 표현했다.

 

dp[i - 1][j] = n

 

i 번째 수(arr[i])가 x라고 하자.

 

그럼 위의 경우에서 i 번째 수까지 계산한 결과는 j - x 또는 j + x 가 된다.

 

여기서 j - x와 j + x는 모두 0 이상 20 이하여야 한다.

 

그리고 i 번째 수까지 계산한 결과가 j - x 또는 j + x 인 경우의 수는 각각 일단 n이다.

 

i - 1 번째 수까지 계산한 결과가 j 가 아닌 다른 수인데, 그 결괏값에 j 를 빼거나 더한 결과가 각각 j + x, j - x일 수도 있다.

 

따라서 점화식은 아래와 같이 나타내었다.

 

dp[i][j - arr[i]] += dp[i - 1][j]

dp[i][j + arr[i]] += dp[i - 1][j]

 

추가로 주의해야 할 점이 있는데, 출력값은 int의 범위를 초과하므로 dp 배열을 long long 형으로 선언해줘야 한다는 것이다.

코드

#include <bits/stdc++.h>
using namespace std;
long long dp[99][21];
int arr[100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j;
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> arr[i];
	dp[0][arr[0]] = 1;
	for (i = 1; i < N - 1; i++) {
		for (j = 0; j <= 20; j++) {
			// arr[i - 1] 숫자까지 계산한 결과가 j인 경우가 있을 때
			if (dp[i - 1][j]) {
				if (j - arr[i] >= 0)
					dp[i][j - arr[i]] += dp[i - 1][j];
				if (j + arr[i] <= 20)
					dp[i][j + arr[i]] += dp[i - 1][j];
			}
		}
	}
	cout << dp[N - 2][arr[N - 1]];
}

 

성능

코드 제출 결과