[백준] Swift 2302 극장 좌석 DP

문제 :

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

2302번: 극장 좌석

 

분석 :

처음에는 VIP 좌석만 따로 1로 배열을 받고 1을 기준으로 나눠 배열을 칸만큼 곱하면(한칸씩 이동하는 경우) 되는거 아닌가 ? 생각했다. 하지만 제출 후 틀리고 보니 배열칸만큼은 두사람끼리만 자리를 바꿨을때더라 ㅎ

만약 

이러한 배열이 있을때

1,2,3,4 중 두 수 예를 들어 1,2만 자리 바꿨을때 모든 수에 대한 경우의 수는 원소의 개수만큼 4이지만

12가 자리를 바꾸는 사이 34도 자리를 바꿀수 있다 그래서 이거는 이렇게 풀면 안되고 다시 DP로 접근하였다.

각 부분 배열에 대해 자리를 바꾸고 부분 배열의 경우의수만큼 곱해준다. 

 

그렇다면 부분 배열에 대한 자리는 어떻게 바꾸는가 ?

점화식 d는 n개의 원소를 가지는 부분 배열에 대해 n번째 원소가 자리를 바꾸는지 안바꾸는지로 경우의수가 나뉜다.

n번째 원소가 자리를 바꾸지 않는다 ❌ : 1 ~ n-1번째 원소에 대해 경우의 수를 생각한다.

n번째 원소가 자리를 바꾼다 🆗 : 그렇다면 n-1번째 원소와 바꿔야 한다 따라서 n-1, n번째 원소를 제외한 1 ~ n-2번째 원소에 대한 경우의수를 생각한다.

따라서 점화식은 아래와 같다.

d[n] = d[n-1] + d[n-2] (생각보다 간단한 점화식이다 기준만 잘세운다면 ..)

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/16.
//

import Foundation
var n = Int(readLine()!)!
var arr = Array(repeating: 0, count: n)
var m = Int(readLine()!)!
for _ in 0..<m {
    let vip = Int(readLine()!)!
    arr[vip-1] = 1
}
var result = 1
for i in arr.split(separator: 1) {
    var d = Array(repeating: 0, count: i.count)
    if i.count == 1 || i.count == 2 {
        result *= i.count
    }else {
        d[0] = 1 // 1명
        d[1] = 2 // 2명
        for num in 2..<i.count {
            d[num] = d[num-1] + d[num-2]
        }
        result *= d[i.count - 1]
    }
}

print(result)