[Algorithm] 백준 DP문제 - 극장 좌석(2302) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 극장 좌석 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

 

1. 풀이 소스

 

import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static final int LEN = 41;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int m = parseInt(br.readLine());

        int[] vip = new int[m]; // 고정석 저장
        int[] dp = new int[LEN]; // dp 초기화 41개 좌석
        
        for (int i = 0; i < m; i++) vip[i] = parseInt(br.readLine()); // vip 입력 받기
        
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; // n번까지 설정
        
        int answer = 1; // n == 1일 때 answer는 1
        
        int preIdx = 0; // 곱셉을 위한 이전 위치
        for (int idx : vip) {
            answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
            preIdx = idx; // 인덱스를 업데이트하여 dp 길이
        }
        
        answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp
        System.out.println(answer);
    }
}

 

2. 풀이 중점 사항

 

점화식 도출

 

앉을 수 있는 좌석은 다음의 규칙이 있습니다.

1번 좌석 : 1 (1)

2번 좌석까지: 1, 2   /   2, 1 (2)

3번 좌석까지: 1, 2, 3   /   1, 3, 2   /   2, 1, 3  (3)

4번 좌석까지: 1, 2, 3, 4  / 1, 3, 2, 4  / 2, 1, 3, 4 /  1, 2, 4, 3 / 2, 1, 4, 3 (5개)

 

이러한 규칙성은 피보나치수열과 같은 점화식을 도출할 수 있습니다.

dp [n] = dp[n - 1] + dp[n - 2]

이를 바탕으로 n개까지의 dp를 구해야 했습니다.

 

고정석 설정하기

 

고정석을 설정하고나면, 고정석 이전 혹은 사이, 이후에 있는 좌석들은 각각 새로운 길이의 좌석이라고 볼 수 있습니다.

 

즉, 인접한 3개, 인접한 1개, 인접한 3개의 좌석의 dp를 구한 후 세 개는 모두 동시에 발생하므로 곱하여 값을 구할 수 있습니다.

이러한 원리를 구현한 코드가  아래의 코드입니다.

 

int answer = 1; // n == 1일 때 answer는 1

int preIdx = 0; // 곱셉을 위한 이전 위치
for (int idx : vip) {
    answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
    preIdx = idx; // 인덱스를 업데이트하여 dp 길이
}

answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp

 

이상으로 극장 좌석 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!