[BOJ5557] 1학년

[BOJ5557] 1학년

문제 링크

문제 풀이

1. 생각의 흐름

• 일단 +,-를 N-2개만큼 사용하여 결과값을 마지막 숫자와 비교해야하기 때문에 모든 경우의 수를 생각해야한다.
• 하지만 모든 경우의 수를 다 보게 될 경우 당연하게도 시간 초과가 발생한다.
• 그러면 모든 경우의 수를 보되, 이미 한번 봤던 경우에 대해서 저장해두고 다시 그 경우를 보게 될 경우 재귀를 더 이상 들어가지 않고 바로 값을 가져다 쓸 수 있도록 DP를 이용하여야 한다.

2. 코드 구현 - 1

• DP배열을 2차원으로 만들어 DP[현재까지 계산된 값][몇번째숫자를보는지]로 만들어준다. 현재까지 계산된 값은 0~20의 범위를 넘어가지 않고, 입력받는 숫자의 개수는 100을 넘기지 않으므로 메모리 걱정은 안해도 된다.
• 재귀를 통하여 결과값이 마지막 숫자와 같은 경우 DP[결과값][N-2]에 1을 추가해준다.
• 그 후, 현재까지의 결과값에 대한 저장된 DP값이 있는 경우 그 값을 사용하고 더 이상 재귀를 들어가지 않는 식으로 구현하였다.

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;

int N;
int ans;
int arr[101];
long long dp[21][101];

void comb(int n) {
	if (n == N - 1) {
		if (ans == arr[N - 1]) dp[ans][n] = 1;
		return;
	}
	long long &ret = dp[ans][n];
	if (ret != -1) return;
	if (ans + arr[n] <= 20) {
		ans += arr[n];
		comb(n + 1);
		ans -= arr[n];
		if (dp[ans + arr[n]][n + 1] != -1) {
			if (ret == -1) ret = 0;
			ret += dp[ans + arr[n]][n + 1];
		}
	}
	if (ans - arr[n] >= 0) {
		ans -= arr[n];
		comb(n + 1);
		ans += arr[n];
		if (dp[ans - arr[n]][n + 1] != -1) {
			if (ret == -1) ret = 0;
			ret += dp[ans - arr[n]][n + 1];
		}
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	memset(dp, -1, sizeof(dp));
	for (int n = 0; n < N; n++) {
		cin >> arr[n];
	}
	ans += arr[0];
	comb(1);
	cout << dp[arr[0]][1] << endl;
	return 0;
}

2. 코드 구현 - 2

• 위의 방법은 DP를 사용한 재귀였고, 아래는 for문을 통해서 앞에서부터 채워나가는 식으로 dp테이블을 구현하였다.
• 아래 방법은 문제 풀때는 생각하지 못하고 끝나고나서 생각나서 구현해봄.

#include <iostream>
#define endl '\n'
using namespace std;

int N;
long long dp[101][21];
int arr[101];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	dp[0][arr[0]] = 1;
	for (int i = 1; i < N - 1; i++) {
		for (int j = 0; j <= 20; j++) {
			if (dp[i - 1][j] == 0) continue;
			if (j + arr[i] <= 20) dp[i][j + arr[i]] += dp[i - 1][j];
			if (j - arr[i] >= 0)dp[i][j - arr[i]] += dp[i - 1][j];
		}
	}
	cout << dp[N - 2][arr[N - 1]] << endl;
	return 0;
}