(백준 ) 백준 저울

문제 요약

전형적인 DP 문제.

• 추가 여러개 주어진다.
• 주어진 추의 합으로 재지 못하는 무게를 출력하라.

원문

솔루션

문제에서 요구하는 사항은 주어진 추의 합으로 재지 못하는 무게의 최소값 이는 주어진 추의 합으로 잴 수 있는 무게를 구하면 역으로 구할 수 있다. 하나의 추로 만들어

상태공간

시간복잡도

추의 개수 1<->1000 추의 무게 1<->1000000 \(10^{3} * 10^{6} = 10^9\)

구현 순서

#include <iostream>
#include <vector>
using namespace std;
/*
* N : 정수의 범위
* K : 정수의 개수
* DP[n][s] = n개의 수로 s를 만드는 경우의 수
*/
int N, K;
long long int DP[211][211] = { 0, };
//r : 사용한 수의 개수
//sum : r개의 수를 사용했을 때 남은 채워야할 수의 합
long long int f(int r, int sum) {
	long long int ret = 0, num = 0;
	
	if (r == K) {
		if (sum == 0) return 1;
		else return 0;
	}

	int i, j;
	for (i = 0; i <= sum; i++) {
		//방문한 적이 없는 경우
		if (DP[r + 1][sum - i] == -1) {
			num += (f(r + 1, sum - i) % (long long int)1e9);
		}
		//방문 했던 경우
		else num += (DP[r + 1][sum - i] % (long long int)1e9);
	}
	//탐색 결과를 저장
	DP[r][sum] = num;
	return num;
}
int main() {
	cin >> N >> K;
	int i, j;
	for (i = 0; i <= 200; i++) {
		for (j = 0; j <= 200; j++) {
			DP[i][j] = -1;
		}
	}
	cout << f(0, N) % (long long int)1e9 << endl;
	return 0;
}

이슈

• 1e9로 나누어 주지 않아 정수 범위를 초과해,,,
  • 자바스크립트와 파이썬에 익숙해지는 바람에 그만,,,