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

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

5557번: 1학년

숫자가 주어졌을 때, +나 -를 끼워서 만들수 있는 올바른 등식의 개수를 출력하는 문제이다. 

문제에서 등식의 개수는  2^63-1 이하라고 명시되어 있으므로 long long형을 이용해야한다.

 

이 문제는 처음에 일차원 dp로 구현하였다.

dp[i] : 현재 시점에서 계산값이 i가 나오는 경우의 수

n : 지금 입력받은 수

dp[i]>0 면,  dp_copy[i+n]+=dp[i] or dp_copy[i-n] +=dp[i]dp_copy를 dp에 복사테케는 다 맞았지만, 아직까지 왜 틀렸습니다가 뜨는지 원인을 찾지 못했다 ㅠㅠ https://www.ioi-jp.org/joi/2010/2011-yo-prob_and_sol/index.html 의 4번문제 테스트케이스를 해보면 N=100일때만 답이 다른것을 확인하였다. 오버플로우 문제인가...? 

 

일단 코드는 아래와 같다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N, n;
long long dp[21] = { 1, };
long long dp_copy[21];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> n;
		if (i == N - 1) {
			cout << dp[n] << endl;
			return 0;
		}
		memset(dp_copy, 0, sizeof(dp_copy));
		for (int j = 0; j < 21; j++) {
			if (dp[j] > 0) {
				int next;
				for (int k = 0; k < 2; k++) {
					if (k == 0) next = j + n;
					else next = j - n;
					if (next >= 0 && next <= 20) {
						dp_copy[next] += dp[j];
					}
				}
			}
		}
		copy(dp_copy, dp_copy + 21, dp);
	}
}

 

따라서, 일차원이 아닌 이차원 dp로 구현하였더니 해결되긴 하였다. 문제풀이 방식은 다음과 같다.

 

dp[i][j] : 0번째부터 i번째 인덱스까지 계산값이 j가 나오는 경우의 수

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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N,n;
long long dp[101][21]; //i번째 인덱스까지 j를 만드는 방법 
int a[101];

//dp[i][j] = dp[i-1][j-a[i]] + dp[i-1][j+a[i]]

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	
	dp[0][a[0]] = 1; //맨처음수
	for (int i = 1; i < N-1; i++) {
		for (int j = 0; j <=20 ; j++) {
			int next;
			for (int k = 0; k < 2; k++) {
				if (k == 0) next = j+a[i]; 
				else next = j - a[i];
				if (next >= 0 && next <= 20) { //범위 내에있으면
					dp[i][next] += dp[i-1][j];
				}
			}
		}
	}
	cout << dp[N - 2][a[N - 1]];
}

일차원이 틀렸던 이유는 더 고민해봐야겠다!

 

---

(추가)

맨처음 dp[0]을 1로 주고 for문을 돌리는것이 아닌, 맨 처음 숫자 n을 사용하여 dp[n]=1로 초기화 시킨후, 그다음부터 for문을 돌리면 처음 짯던 코드로 해결이 되었다!

 

원인은 이거였다. 맨처음 dp[0]=1로 초기화 시키면, 맨 처음 입력 숫자가 0일때 문제가 생긴다. 애초에 dp[0]=1에서 시작하기 때문에, 0이 들어오는 경우 0+0=0인 경우와 0-0=0인 경우로 dp[0]이 1이 아닌 2로 업데이트 되버린다.

 

원인을 찾아준 스터디원분께 감사의 말씀을 ㅠㅠ

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N, n;
long long dp[21];
long long dp_copy[21];

int main() {
	cin >> N;
	cin >> n; dp[n] = 1;
	for (int i = 1; i < N; i++) {
		cin >> n;
		if (i == N - 1) {
			cout << dp[n] << endl;
			return 0;
		}
		memset(dp_copy, 0, sizeof(dp_copy));
		for (int j = 0; j < 21; j++) {
			if (j + n <= 20) dp_copy[j + n] += dp[j];
			if (j - n >= 0) dp_copy[j - n] += dp[j];
		}
		copy(dp_copy, dp_copy + 21, dp);
	}
}