[백준] DP - 11726번 2xN 타일링

11726번: 2×n 타일링

입력 

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

2 * 1  = 1
2 * 2 = 2
2 * 3 = 3

2 * 4 = 5
가로가 0개인 경우 ㅁㅁㅁㅁ = 1
가로가 1개인 경우 ㅁㅁ-- = 3
가로가 2개인 경우 ---- = 1

2 * 5 = 8 
가로가 0개인 경우 ㅁㅁㅁㅁㅁ = 1
가로가 1개인 경우 ㅁㅁㅁ--  = 4
가로가 2개인 경우 ㅁ----   = 3

반복되는 규칙이 보인다
dp[i] = dp[i-1] + dp[i-2]
문제에서는 10007으로 나눈 값을 요구하기에 이에 10007을 나누어준다 

 

Swift 전체 코드

let input = Int(readLine()!)!
var dp = Array(repeating: 1, count: 1001)

for i in 2..<input+1 {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
}

print(dp[input])