Swift) 백준 11727 (2 x n타일링2)

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

 

코드설명 : 

n이 1 ~ 3일때를 그림으로 보자

 

문제를 보면 1x2, 2x1, 2x2짜리 타일들을 쓴단다.

그 타일들을 기준잡아서 규칙을 세워봤다.

n = 1일 때와 n = 2일 때는 완벽한상태(?)가 아니기 때문에 저걸가지고 규칙을 이야기할수는 없다.

그래서 n = 4까지 손으로 그려봤고 그 결과 위와 같은 규칙이 나왔다.

 

n = 4 이니까 n -1 한 값인 n = 3일 때의 도형들이 2x1도형옆에 붙어서나온거고 n - 2 두개도 같은원리다.

 

 

후기 : 나도 이 문제이해를 참 어렵게했다. 설명이 죄다 대충이고 제대로 이해도안하고 글쓰신분들도 많은거 같아서..

길이가 n인데 1빼서 n -1 인거 가지고 DP문제인걸 어떻게 알겠나 싶었다  ㅋㅋ

왜 DP를 쓰고, 왜 n-1 인지를 잘모르는 사람들은 이해하기 어렵게 해놨던데.. 이 글을보고 이해했으면 좋겠다. 

 

let n = Int(readLine()!)!
var arr = Array(repeating: 0, count: 1001)

arr[1] = 1
arr[2] = 3

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