[JAVA] BOJ(백준) - 극장 좌석 - 2302

문제내용

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

2302번: 극장 좌석

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1)

 

---

문제 접근 방법

오랜만에 보는 DP 문제이다.

DP문제를 풀기 전에 DP문제가 맞는지 부터 확인해야 한다.

 

DP문제 맞는지 확인

1. 작은 문제의 반복
   작은 문제의 반복이란 쉽게 말하면 어떤 로직을 해결하기 위해 부분적인 문제를 해결했는데 후에 똑같은 문제가 계속 나오고 이전 문제에서 해결한 값이 다시 쓰이는 경우를 말한다. (ex. 피보나치 수열 .. )
   이 문제에서 예를들면
   입장권이 4개이고 F(4)를 구한다고 가정했을 때 F(4) = F(3) + c (4를 추가한 경우의 수) 가된다.
   입장권이 3개이고 F(3)을 구한다고 가정했을 때 F(3) = F(2) + c (3를 추가한 경우의 수) 가된다.
   입장권이 2개이고 F(2)을 구한다고 가정했을 때 F(2) = F(1) + c (2를 추가한 경우의 수) 가된다.
   입장권이 1개이고 F(1)을 구한다고 가정했을 때 F(1) = 1이 된다.
2. 조건이 어떻게 되든 초기값은 일정
   DP문제는 초기값이 일정하기 때문에 이전에 계산해서 쓰인값을 다시 쓸때 결과값이 같아지게 된다.
   이문제도 마찬가지로 초기값이 일정하기 때문에 후에 나오는 결과값이 같아지게 된다.
   이부분은 이따가 코드를 보며 생가해보자.

DP 문제가 맞는지 확인했다면 메모이제이션을 하기 위해 일정한 규칙을 갖고있는 점화식을 세워야한다.
내가 점화식을 세우는 과정은 아래와 같다.

 

점화식 세우는 과정

1. DP 배열 정의하기
   DP배열을 1차원 배열로 할지, 2차원 배열로 할지, 인덱스는 어떤의미를 갖고 넣을지, N번째 인덱스에 해당하는 요소값은 어떤의미를 갖는 값인지 생각하고 적절하게 정의해준다.
   사실 이부분은 정말 머리가 좋은 사람들 제외하고는 문제를 많이 풀어보고 풀려는 문제의 요구를 잘 이해해야 정의하기가 그나마 쉬워진다 생각한다.
   
   
2. 노가다
   이전에 풀어봤던 규칙 혹은 비슷했던 것들을 제외하고는 문제를 보고 한눈에 점화식이 들어오지 않는다.
   따라서 나는 제일 작은부분 부터 하나씩 직접 계산해보면서 규칙을 찾으려고 하는 편이다.
   이렇게하면 개인적으론 내가 써놓은 값들을 보며 DP배열을 재정의 할수도 있고 내가 정의 했던 DP배열을 어떻게 사용해야 할지 좀더 정확하게 알수있다.
   
   

나는 위와같은 방법으로 DP문제에 접근하고 이문제의 풀이과정은 아래와 같다

 

풀이과정

1. DP 문제가 맞는지 확인
   이부분은 위에서 설명했다.
   
   
2. DP 배열 정의
   나는 Integer[] dp = new Integer[N+1] 로 dp 배열을 정의했고
   인덱스 = 입장권 개수
   요소값 = 입장권 개수에 따라 앉을수 있는 경우의 수
   라고 생각하고 사용했다.
   크기를 N+1로 한 이유는 1번~N번 까지 입장권번호에 맞게 인덱스를 사용하기 위해서이고,
   int가 아닌 Integer로 한이유는 초기값을 null로 해주기 위해서이다.
   
   
3. 초기화 하기
   dp배열을 정의하고 가장 작은 값에대해 초기화를 해줘야 한다.
4. 점화식 세우기
   -vip 좌석이 없을때
   

   입장권 개수(N)	1	2	3	4	5
   경우의 수	1	1 2, 2 1	1 2 3, 2 1 3, 1 3 2	1 2 3 4,  2 1 3 4, 1 3 2 4, 2 1 4 3, 1 2 4 3	1 2 3 4 5,  2 1 3 4 5,  1 3 2 4 5, 2 1 4 3 5, 1 2 4 3 5, 2 1 3 5 4, 1 3 2 5 4, 1 2 3 5 4
   dp[N]	1	2	3	5	8

   vip 좌석이 없을때는 다음과 같은 결과가 나온다. 위의 결과는 우리가 아는 피보나치 수열과 비슷하다.
   따라서 이때 점화식은 dp[N] = dp[N-1] + dp[N-2] 라고 말할 수 있다.
   
   하지만 vip 좌석이 있을경우는 다르다
   -vip좌석이 있을때(4번이 vip)

   입장권 개수(N)	1	2	3	4	5	6
   경우의 수	1	1 2, 2 1	1 2 3, 2 1 3, 1 3 2	1 2 3 4,  2 1 3 4, 1 3 2 4,	1 2 3 4 5 2 1 3 4 5 1 3 2 4 5	1 2 3 4 5 6, 2 1 3 4 5 6, 1 3 2 4 5 6, 1 2 3 4 6 5, 2 1 3 4 6 5, 1 3 2 4 6 5
   dp[N]	1	2	3	3	3	6

   vip 좌석은 고정좌석이기 때문에 경우의수가 나눠진다.
   1. N이 vip 좌석일 때 경우의 수(마지막 좌석이 vip일때를 고려)
      dp[N] = dp[N-1]
   2. N-1이 vip 좌석일 때 경우의 수
      dp[N] = dp[N-2]
   3. N-2가 vip 좌석일 때 경우의 수
      dp[N] = dp[N-1]*2
   4. N-1과 N-2가 vip 좌석이 아닐때( 일반적인 경우 )
      dp[N] = dp[N-1] + dp[N-2]

위의 과정으로 문제를 풀수 있다.

자세한 내용은 풀이를 보자.

 

---

풀이

TopDown

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

public class Main {
	static Integer[] dp; //2번 -> dp배열 , dp[입장권 개수] = 앉을수 있는 경우의 수
	static HashMap<Integer, Integer> vip = new HashMap<Integer, Integer>();//vip 좌석
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());//총 좌석수
		int M = Integer.parseInt(br.readLine());//vip 좌석수 
		dp = new Integer[N+1];//0번~N번 까지 크기로
		
		for(int i=0; i<M; i++) {//vip좌석 넣기
			vip.put(Integer.parseInt(br.readLine()), 0);
		}
			
		//3번 -> 초기화
		dp[0]=0;
		dp[1]=1;
		//입장권이 2번까지 왔을때 초기화
		//vip좌석은 옮길수 없음. 따라서 1번 좌석이 vip라면
		//입장권이 2번까지 왔을때 경우의수는 1개임
		if(vip.containsKey(1)) dp[2]=1;
		else dp[2]=2;
		
		System.out.println(seat(N));//정답 출력
	}
	
	//4번 -> N까지 앉을수 있는 좌석의 경우의수 계산
	public static int seat(int N) {
		if(dp[N]==null) {//null일때 계산
			if(vip.containsKey(N)) {//마지막 자리가 vip일때
				dp[N] = seat(N-1);
			}else if(!vip.containsKey(N-1) && !vip.containsKey(N-2)) {//vip좌석이 아닐때
				dp[N] = seat(N-1)+seat(N-2);
			}else if(vip.containsKey(N-1)) {//첫번째 전이 vip좌석일때
				dp[N] = seat(N-2);
			}else if(vip.containsKey(N-2)) {//두번째 전이 vip좌석일때
				dp[N] = seat(N-1)*2;
			}
		}
		
		return dp[N];
	}
}

 

Bottom Up

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

public class Main {
	static Integer[] dp;
	static HashMap<Integer, Integer> vip = new HashMap<Integer, Integer>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		dp = new Integer[N+1];
		
		for(int i=0; i<M; i++) {
			vip.put(Integer.parseInt(br.readLine()), 0);
		}
		
		dp[0]=0;
		dp[1]=1;
		if(vip.containsKey(1)) dp[2]=1;
		else dp[2]=2;
		
		System.out.println(seat(N));
		
	}
	
	public static int seat(int N) {
		for(int i=3; i<=N; i++) {
			if(vip.containsKey(i)) {
				dp[i] = dp[i-1];
			}else if(!vip.containsKey(i-1) && !vip.containsKey(i-2)) {
				dp[i] = dp[i-1] + dp[i-2];
			}else if(vip.containsKey(i-1)) {
				dp[i] = dp[i-2];
			}else if(vip.containsKey(i-2)) {
				dp[i] = dp[i-1]*2;
			}
		}
		return dp[N];
	}
}

---

마치며

일반적으로 dp문제를 풀때 재귀로 먼저 풀고 for문으로 푸는것을 추천한다.

이유는 재귀로 풀어낸것은 for문으로 무조건 풀어낼수 있다고 배웠기 때문이다.