[BOJ 백준] 제단 (5626) Java

링크 : https://www.acmicpc.net/problem/5626

 

문제 설명 : 

상근이는 성적 향상을 기원하며 N열짜리 제단을 만들기로 했다.

제단의 각 열의 높이는 모두 정수이며, 가장 처음에 모든 열의 높이는 0이다. 제단은 다음과 같은 과정을 통해서 만들어진다. 먼저, 같은 높이를 가지는 연속하는 열을 선택한다. 그 다음, 선택한 첫 열과 마지막 열을 제외한 모든 열의 높이를 1만큼 올린다.

아래 그림은 제단을 쌓는 과정의 예시이다.

수백년이 흐르는 동안 많은 도둑들이 제단의 일부 열을 훔쳐갔다. 상근이의 손자의 손녀의 손자의.... 손녀는 남은 제단의 높이를 가지고, 가능한 제단의 경우의 수를 세려고 한다.

제단의 높이가 주어졌을 때, 남아있는 제단의 높이와 일치하는 제단의 개수를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 제단의 열의 수 N이 주어진다. (1 ≤ N ≤ 10,000)

다음 줄에는 공백으로 구분된 N개의 정수 hi가 주어진다. (-1 ≤ hi ≤ 10,000) hi는 i번 열의 높이를 나타내며, -1인 경우에는 도둑이 그 열을 훔쳐간 상태를 나타낸다.

 

출력 : 

첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 

예제 입력 : 

6

-1 -1 -1 2 -1 -1

 

예제 출력 : 

3

 

 

접근법 : 

1) 어떻게 풀 것인가?

문제 조건 몇가지를 정리해봤다. 

① 첫 열과 마지막 열의 높이는 0이다.
② 인접열의 높이 차이는 1 
→ 각 열의 가능한 높이 <= min(i, (N-1) -i )
1번째열    : 0
2번째열    : 0, 1
3번째열    : 0, 1, 2

i번째열    : 0, 1, .... min(i, (N-1) -i )

N-2번째열 : 0, 1, 2
N-1번째열 : 0, 1
N번째열    : 0

 

dp[ i ][ j ] = i번째 열의 높이가 j일때 i번째 열까지의 가능한 제단 경우의 수 

로 정의하고

 

높이를 모르는 상태(-1) 라면 아래 코드와 같이 점화식을 세우고

			// 2-1. 높이를 모르는 상태 - 0 ~ min(i, (N-1)-i) 가능
			if (input[i] == -1) {
				len = Math.min(i, (N-1)-i);
				for (int j = 0; j <= len; j++) {
					
					// 인접 열 높이 대비 +/- 1 높이만 가능
					for (int k=-1; k<=1; k++) {
						int adjHeight = j + k;
						if (adjHeight < 0) continue;
						
						dp[i][j] += dp[i-1][adjHeight];
						dp[i][j] %= MOD_NUMBER;
					}
				}
			}

 

높이를 아는 상태라면 아래 코드와 같이 점화식을 세우면 된다.

			// 2-2. 높이를 아는 상태
			else {
				for (int k=-1; k<=1; k++) {
					int adjHeight = input[i] + k;
					if (adjHeight  < 0) continue;
					
					dp[i][input[i]] += dp[i-1][adjHeight];
					dp[i][input[i]] %= MOD_NUMBER;
				}
			}

 

전체 코드는 아래 참고.

 

2) 시간복잡도

최대 O(N^2/2) 정도 되는 것 같은데 가지치기가 많이 되서인지 시간은 여유있는 편이다.

(Java 기준 -  816ms)

 

3) 공간복잡도

dp 배열 선언시 int [N][N]을 하면 10,000*10,000*4Bytes = 약 380MB로 초과가 예상된다.

int [N][(N/2)+2] 로 아껴서 통과했다.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

 2차원 DP 코드 작성법

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 14003 가장 긴 증가하는 부분 수열 5
public class Main {

	static int N;
	static int[] input;
	static int[][] dp;               // dp[ i ][ j ] = i번째 열의 높이가 j일때, i번째 열까지 가능한 제단 경우의 수 

	static final int MOD_NUMBER = 1000000007;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 1. 입력받기
		N = Integer.parseInt(br.readLine());
		input = new int[N];
		dp = new int[N][(N / 2) + 2];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
			// 불가능한 경우 거르기
					
			if (input[i] > Math.min(i, (N - 1) - i)) {
				System.out.println(0);
				br.close();
				return;
			}
		}

		// 2. dp 실행
		//   dp[ i ][ j ] = i번째 열의 높이가 j일때, i번째 열까지 가능한 제단 경우의 수 
		dp[0][0] = 1;
		int len;
		for (int i = 1; i < N; i++) {

			// 2-1. 높이를 모르는 상태 - 0 ~ min(i, (N-1)-i) 가능
			if (input[i] == -1) {
				len = Math.min(i, (N-1)-i);
				for (int j = 0; j <= len; j++) {
					
					// 인접 열 높이 대비 +/- 1 높이만 가능
					for (int k=-1; k<=1; k++) {
						int adjHeight = j + k;
						if (adjHeight < 0) continue;
						
						dp[i][j] += dp[i-1][adjHeight];
						dp[i][j] %= MOD_NUMBER;
					}
				}
			}
			
			// 2-2. 높이를 아는 상태
			else {
				for (int k=-1; k<=1; k++) {
					int adjHeight = input[i] + k;
					if (adjHeight  < 0) continue;
					
					dp[i][input[i]] += dp[i-1][adjHeight];
					dp[i][input[i]] %= MOD_NUMBER;
				}
			}
		}

		// 3. 정답 출력
		System.out.println(dp[N-1][0] % MOD_NUMBER);
		br.close();
	}
}