c++/알고리즘

[c++] 백준-제단 5626

hojung 2023. 1. 25.

728x90

문제

입력과 출력

사실 이 문제를 풀 때 DP를 이용해서 푸는 문제라는 것을 알고 있었기 때문에 쉽게 접근할 수 있었다. (물론 난이도 자체는 어렵다 매우)

DP는 점화식을 세우면 끝나는 문제다.

문제를 파악해보면 다음과 같다.

문제 해설

우선 제단을 세울 수 있는 경우를 생각해보았다.

	x	가능	가능	x
x	가능	가능	가능	가능	x

점화식은 대부분 memoization된 이전 상태에서 현재의 값을 찾아낼 수 있기에 두 가지의 경우만을 고려해보았다.

2층의 가능한 경우는 1층의 경우에 따라 가능할 수도 불가능할 수도 있다. 따라서 이는 현재 상태가 이전 관계에 영향을 받는 점화식으로 풀 수 있는 DP문제이다.

그렇다면 현재 상태는 이전 상태의 어떠한 영향을 받을까?

다음 세 가지 경우가 있을 수 있다.

현재 제단이 이 전의 제단보다 한 칸 더 쌓여서 1칸 높은 경우
현재 제단이 이 전의 제단과 높이가 같은 경우
현재 제단이 이전의 제단보다 높이가 낮은 경우

위 세 가지 경우의 수는 각각의 독립된 상황으로 현재 제단이 이전의 제단보다 높거나 같을 수 없다. 또한 같거나 작을수도 높거나 작을수도 없다. 따라서 각각의 경우는 모두 더하는 것이 현재의 경우의 수를 구할 수 있는 방법이다.

이 과정에서 이러한 점화식을 도출할 수 있다.

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

기본적인 점화식은 다음과 같다. 그 후 어떤 점을 생각해줘야할까?

제단 열 별 높이

우선 제단의 열 별 가능 높이가 있겠다.

4
3
2			2	2
1		1	1	1	1
0	0	0	0	0	0	0
열 번호	0	1	2	3	4	5

위의 표를 살펴보자 가운데를 중심으로 양 끝에 더 가까운 만큼이 최대 높이와 같다. 따라서 가능 높이를 난 이렇게 표시해주었다.

#include <algorithm>

//가능 높이 
min(i , N-i-1);

따라서 높이의 경우 모든 높이를 보는 것이 아니라 저 높이가 넘을 경우 반복문의 실행을 중지 시켜주면 되는 것이다.

Edge Case

나는 지금 현재

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

위와 같은 점화식을 이용하고 있다.

하지만 j가 0인 경우는 out of Memory(잘못된 주소를 읽을 때 나는 오류)가 날 것이다.

따라서 j==0인 경우 예외 처리를 해줘야한다.

따라서 완성된 코드는 다음과 같다.

완성 코드

#pragma warning (disable : 4996)
/*
	문제를 생각해보면 다음과 같다. 
	0번째 : 0만가능
	1번째 : 0 1 가능
	2번째 : 0 1 2 가능 
	k번째 : 0 1 2 ... k 가능 

	-1인 경우는 도둑이 훔쳐간 상태이다. 
	-1인 경우에 도둑은 한 번에 하나만 가져간다는 말은 없으며 그냥 열을 통째로 가져간듯 하다.
	제단의 높이가 정해지는 경우는 세 가지가 존재한다. 
	1. 이전 제단의 높이보다 낮을 경우
	2. 이전 제단의 높이와 같을 경우
	3. 이전 제단의 높이보다 높을 경우

	10000 * 4byte = 40000 byte = 40KByte * 10000 = 400,000KByte = 400MB
	메모리 초과가 나게 된다. 따라서 높이에 해당하는 DP배열의 사이즈를 줄여줘야한다. 

	메모리 제한이 256MB이므로 10000 * 4byte = 40KB * 5000 = 200MB //메모리 제한 만족한다. 
	c++에서는 pageFault문제 때문에 열로 메모리를 탐색하는 것이 효율이 좋다. 따라서 높이에 해당하는 부분을 높이로 만들어준다. 
*/
#include <cstdio>
#include <algorithm>
#define MAX 10000+2
#define MOD 1000000007
using namespace std;
int N; // 제단의 열의 수
int inputs[MAX];
int dp[MAX][5001]; // 제단 열 높이 
int ans;
void makeDP() {
	//초기 값 설정
	dp[0][0] = 1; // 맨 왼쪽 높이 0은 1로 초기화한다. 
	for (int i = 1; i < N; i++) {
		if (inputs[i] == -1) {
			//만약 도둑맞은 제단이었다면 다음과 같이 가능한 높이까지 모두 채워준다.
			for (int j = 0; j <= min(i, N - i - 1); j++) {
				//i를 열로 생각해야한다.
				if (j == 0) {
					dp[i][j] += dp[i - 1][j];
					dp[i][j] %= MOD;
					dp[i][j] += dp[i - 1][j + 1];
					dp[i][j] %= MOD;
				}
				else {
					 // 아니라면 세 가지 경우를 모두 생각해주어야 한다.
					dp[i][j] += dp[i - 1][j];
					dp[i][j] %= MOD;
					dp[i][j] += dp[i - 1][j + 1];
					dp[i][j] %= MOD;
					dp[i][j] += dp[i - 1][j - 1];
					dp[i][j] %= MOD;
				}
			}
		}
		//만약 입력받은 높이가 -1이 아니었다면 
		else {
			//해당하는 열, 높이 위치의 배열 칸에다가 값을 넣어줘야한다.
			if (inputs[i] == 0) {
				dp[i][inputs[i]] += dp[i - 1][inputs[i]];
				dp[i][inputs[i]] %= MOD;
				dp[i][inputs[i]] += dp[i - 1][inputs[i] + 1];
				dp[i][inputs[i]] %= MOD;
			}
			else {
				dp[i][inputs[i]] += dp[i - 1][inputs[i]];
				dp[i][inputs[i]] %= MOD;
				dp[i][inputs[i]] += dp[i - 1][inputs[i] + 1];
				dp[i][inputs[i]] %= MOD;
				dp[i][inputs[i]] += dp[i - 1][inputs[i] - 1];
				dp[i][inputs[i]] %= MOD;
			}
		}
	}
	ans = dp[N - 1][0] % MOD;
}

int main() {

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &inputs[i]); // 인풋 입력
		//만약 입력받은 높이가 min(i, N - i - 1)보다 크다면 바로 0을 리턴한다.
		if (inputs[i] > min(i, N - i - 1)) {
			printf("%d\n", 0);
			return 0;
		}
	}
	makeDP();
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j <= min(i, N - 1 - i); j++) {
			printf("%d ", dp[i][j]);
		}
		printf("\n");
	}*/
	printf("%d\n", ans);
	return 0;
}