[백준][Kotlin] 2302번 극장 좌석

해당 문제는 DP 문제였습니다.

 

해당 문제에서 빈자리 별 경우의 수를 구하는 점화식은 arr[i] = arr[i-2] + arr[i-1] 입니다.

 

사람마다 다를 수 있겠지만 저의 경우는 빈자리의 갯수만큼 나올 수 있는 경우의 수를 저장한 배열을 생성하고,

고정석의 자리를 확인하면서 빈자리의 개수를 확인하여 발생 할 수 있는 경우의 수를 구하는 방식으로 코드를 작성하였습니다.

 

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.StringTokenizer

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    //var st = StringTokenizer(br.readLine())

    // 좌석의 개수
    val N = br.readLine().toInt()
    // 고정석의 개수
    val M = br.readLine().toInt()
    val arr = IntArray(41){0}
    arr[1] = 1
    arr[2] = 2
    for(i in 3 .. 40){
        arr[i] = arr[i-2] + arr[i-1]
    }

    var result = 1
    var num = 0

    repeat(M){
        val fix = br.readLine().toInt()
        if(fix-1-num != 0){
            result *= arr[fix-num-1]
        }
        num = fix
    }

    if(N-num != 0){
        result *= arr[N-num]
    }

    bw.append("$result")

    bw.flush()
    bw.close()
}