[백준] 2302 극장 좌석 - 동적계획법(DP, Dynamic Programming) + 수학(Math) JAVA

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

2302번: 극장 좌석

코드설명

동적계획법(DP, Dynamic Programming) + 수학(Math) 을 활용합니다.

 

문제에서 VIP를 제외한 사람들의 경우의 수를 동적계획법으로 구하고, 각 구한 가능한 자릿수를 구간별로 곱해주면 됩니다. 이때 각 구간별로 곱해준다는 점에서 수학이라는 태그도 넣어줬습니다.

처음에는 사람들의 자릿수를 생각할때 Combination 을 활용하여 4C3 이런식으로 뭔가 조합을 활용할 수 있을 것 같아서 고민했는데, 1번 좌석을 만약 바꿔준다고하면, 2번 좌석을 사용못하고 3번좌석으로 넘어가야한다는점에서 동적계획법을 활용한 모든 가지수 세기 문제와 연관된다는 것을 알 수 있었습니다.

 

관련 풀이입니다.

 

문제는 점화식을 구하여서 진행합니다.

이번 문제에서 dp[N]은 N번째 자리일때 나올 수 있는 경우의 수를 의미합니다.

즉 dp[10]이라면 10번째 자리일떄 나올 수 있는 전체 경우의 수입니다.

아래처럼 1번째일떄 나올 수 잇는 경우의 수, 2번째. 3번쨰.. 를 구했습니다.

dp[0] = 1;
dp[1] = 1; // 1
dp[2] = 2; //12, 21
dp[3] = 3; //123, 213, 132
dp[4] = 5; //1234, 2134, 1324, 1243, 2143

구하다 보면 피보나치 수열과 같은 점화식이 구해집니다.

for(int i=5; i<=N;i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

그리고 VIP 로 정해진 좌석을 기준으로 나올 수 있는 경우의 수를 독립된 사건으로 봅니다.

그렇기에 문제예시처럼  만약 VIP가 2명씩 있다면, 

9
2
4
7

dp[3] * dp[2] * dp[2] = 3 * 2 * 2 =  12 로 정답이 나옵니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static int N, M;
	public static int[] dp = new int[41]; //이번 문제에서 dp[N]은 N번째 자리일때 나올 수 있는 경우의 수를 의미한다.
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	dp[0] = 1;
    	dp[1] = 1; // 1
    	dp[2] = 2; //12, 21
    	dp[3] = 3; //123, 213, 132
    	dp[4] = 5; //1234, 2134, 1324, 1243, 2143
    	
    	
    	for(int i=5; i<=N;i++) {
    		dp[i] = dp[i-1] + dp[i-2];
    	}
    	
    	answer = 1;
    	int beforeSeatIdx = 0;
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int vip = Integer.parseInt(st.nextToken());
    		answer *= dp[vip - beforeSeatIdx - 1]; //각 자리수의 길이를 의미한다. 이는 N번째 자리일때 나올 수 있는 자리의 경우의 수이다.
    		beforeSeatIdx = vip; //현재 자리수를 저장하기 위한 변수이다.
    	}
    	
    	answer *= dp[N - beforeSeatIdx];
    	System.out.println(answer);
    }
}

 

재귀와 메모이제이션을 활용해서도 가능합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[] arr = new int[41];
	static int[] cache = new int[41];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		Arrays.fill(cache, -1);
		int answer = 1;
		int head = 1;
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int vip = Integer.parseInt(st.nextToken());
			answer *= DFS(vip - head);
			head = vip + 1;
		}
		answer *= DFS((N + 1) - head);
		
		System.out.println(answer);
	}
	
	static int DFS(int now) {
		if(now == 0) return 1;
		if(cache[now] != -1) return cache[now];
		
		int ret = 0;
		if(now - 2 >= 0)
			ret = DFS(now - 2);
		
		ret += DFS(now - 1);
		return cache[now] = ret;
	}
}