[백준] 5557 1학년

5557번: 1학년

 

boj.kr

풀이

동적계획법으로 해결해야하는 문제이다. 문제를 읽고 단순하게 생각하면 DFS를 사용해서 해결할 수 있을 것 같지만, DFS를 사용하면 최대 O(2^100)의 복잡도를 가지기 때문에 시간초과가 발생한다.

따라서 다른 방법을 고민해봐야하는데, 문제에 중간에 나오는 수 모두 0 이상 20 이하라는 말이 나온다. 이 점을 이용해서 dp[숫자 인덱스][중간의 나오는 수]는 숫자 인덱스까지 수를 더했을 때 중간의 나오는 수가 될 수 있는 가지수를 구할 수 있다.

코드

C++

	#include <iostream>
	using namespace std;
	int n;
	long long ans;
	int num[101];
	long long dp[101][21];
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	cin >> num[i];
	dp[1][num[1]]++; // 첫 번째 숫자만으로 num[1]을 만들 수 있는 가짓수는 1가지
	for (int i = 2; i <= n; i++) {
	// 중간에 나오는 수가 모두 0 이상 20 이하이어야하므로 0부터 20까지만 반복한다
	for (int j = 0; j <= 20; j++) {
	if (dp[i - 1][j]) {
	// i 번째 숫자까지 사용해서 j + num[i]를 만들 수 있는 가짓수 계산
	if (j + num[i] <= 20) dp[i][j + num[i]] += dp[i - 1][j];
	// i 번째 숫자까지 사용해서 j - num[i]를 만들 수 있는 가짓수 계산
	if (j - num[i] >= 0) dp[i][j - num[i]] += dp[i - 1][j];
	}
	}
	}
	cout << dp[n - 1][num[n]] << '\n';
	return 0;
	}

view raw 5557.cpp hosted with ❤ by GitHub