[백준] (Swift) 11726번 - 2xn 타일링 (DP 기초 문제, 동적계획법 풀이)

문제 링크

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

11726번: 2×n 타일링

 

내가 푼 풀이

처음에도 이게 왜 동적계획법인지 몰랐다. 인터넷을 대충 참고해보니, 타일링 갯수가 늘어나는 규칙이 피보나치와 닮아있다는 사실을 발견하면 쉽게 풀릴 수 있다고 했다.

정말, 그림을 그리며 풀이과정을 생각해보니 일정한 규칙대로, 피보나치 수열의 형태로 숫자가 증가함을 알 수 있었다. 그래서 bottom up 방식으로 for 문을 이용하여 풀었다.

• dp 문제에서 기억할 것은, dp 배열은 항상, 경우의 수가 들어간다. dp[9] 이면 9번 위치일때의 경우의 수가 value 로 들어간다. 따라서 해당 문제에서는 dp[1]일 경우, 2x9 타일일 때 타일링 경우의 수가 배열로 들어간다는 것이다.
• 해당 문제는 피보나치 수열의 형태를 띈다. 아래 그림을 보자.

이렇게 피보나치 수열로 9까지 계산해보면, 55가 되는 것을 알 수 있다. 이는 백준에서 주어진 예제 인풋-예제 출력과 일치한다. 그러므로 이 규칙을 토대로 코드로 작성했다!

피보나치를 dp 로 구현하는 방식은 이 포스팅을 보길 바란다.

 

첫번째 풀이 - 런타임 에러

let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: n+1)

dp[1] = 1
dp[2] = 2

for i in stride(from: 3, through: n, by: 1) {
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
}

print(dp[n])

 

두번째 풀이 - 맞았습니다!

백준에서 런타임 에러는 예상치 못하게 중간에 프로그램이 중단된 것을 의미한다. 왜 중단됐을까? 분명 어느 테스트 케이스에서 정확한 정답을 출력하지 못하고, 중단 됐을 것이다.

코드를 살펴보던중, 첫번째 풀이 처럼 작성하게 되면, n이 1일 때, dp[i] = dp[i-1] + dp[i-2] 이 부분에서 에러가 발생할 것이라는 것을 찾아냈다. 그래서 고정값으로 넣어두는 dp[1] 과 dp[2]에 대한 출력에 대해서 if 문을 활용하여 따로 작성해주었다.

let n = Int(readLine()!)!
var dp = [Int](repeating: 0, count: n+1)


if n == 1 {
    print(1)
} else if n == 2 {
    print(2)
} else {
    dp[1] = 1
    dp[2] = 2
    for i in 3..<n+1 {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
    }
    print(dp[n])
}