직사각형배치의경우의수

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• N = 3인 경우, 2 x 1의 타일로 2 x 3의 타일을 채울 수 있는 경우의 수를 구해야 함
• 오른쪽 끝의 2 x 1 타일이 세워져 있는 경우와, 누워 있는 경우를 생각해보았을 때, 세워져 있는 경우는 앞의 2개의 2 x 1 타일도 세워져 있어야 하는 경우와 앞의 2개의 2 x 1 타일이 층으로 나누어져 있는 경우에 나머지 2 x 1 타일을 1개 세우는 경우로 볼 수 있으므로 즉, 2 x 2의 타일을 채워야 하는 경우의 수와 같음
• 누워져 있는 경우는 혼자 누워져 있을 수 없으므로 2개가 층으로 나누어져 있고, 앞에 2 x 1 타일 1개가 세워져 있을 수 밖에 없음 즉, 2 x 1의 타일을 채워야 하는 경우의 수와 같음
• 따라서 위 경우의 수를 모두 더한 값이 2 x 3을 채울 수 있는 모든 경우의 수임을 알 수 있고, 2 x 2, 2 x 1의 타일을 채워야 하는 경우의 수의 합이므로 전형적인 동적 계획법이며 피보나치 수열임을 알 수 있음

5. 전체 코드

//MARK: - 직사각형배치의경우의수

//MARK: - Framework
import Foundation

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    
    let baseCondition: Int = 2
    var T: [Int] = Array(repeating: 0, count: N + 10)
    
    //MARK: - Process
    //1. 부분 문제를 정의한다.
    //T[i] = 2 x 1 모양의 타일로 2 x i 크기의 타일을 채울 수 있는 모든 경우의 수
    
    //2. 점화식을 세운다.
    //T[i] = T[i - 1] + T[i - 2] -> 피보나치 수열
    for i in 1...baseCondition {
        T[i] = i
    }
    
    for i in stride(from: baseCondition + 1, through: N, by: 1) {
        T[i] = (T[i - 1] + T[i - 2]) % 1000007
    }
    
    //MARK: - Output
    print(T[N])
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.