Swift) 백준 11726번 (2 x n타일링)

요구능력 : 규칙을 통해 DP를 사용해야할지를 아느냐

 

코드설명 : 

 

2 x 2 ~ 2 x 4까지 그림을 그려보자.

 

규칙을 찾아보면 아래와 같다.

보다시피 위의 세로막대기가 왼쪽에 1개 있는건 n-1개가 나온다.

아래의 가로막대기가 왼쪽에 2개 있는건 n-2개가 나온다.

 

여기서 DP를 해야겠다는 생각이 어떻게 나오냐?

1. 문제가 연속적이다.

2. 중복되는 부분문제가 있다. ( f(5)를 구하려면 f(4)와 f(3)을 구해야하는데 f(4)를 구하려면 f(3)을 또 구해야하는 것을 말한다.)

 

후기 : 규칙을 찾고 DP개념만 알고있으면 풀 수 있는 문제

 

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: 1001)
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])")