[Swift][DP] 백준 2193번 (이친수)

요구능력 : DP를 알고 있느냐

 

코드설명 : 

 

우선 dp로 풀게된 이유는 DP파트에 있어서  규칙을 찾아보니까 연속되는 부분문제가 있었고 쭉 연관되었다.

문제에 나온 규칙대로 N = 5일 때 까지 나열해보자.

 

N = 1

1

 

N = 2

10

 

N = 3

100

101

 

N = 4

1000

1001

1010

 

N = 5

10000

10001

10010

10100

10101

 

여기서, 중요한점은 당연한 부분을 제외하고 보면 답이 나온다는 것이다.

규칙을 보면 앞에 0이 나오면 안되고 1은 연속되면 안된단다.

그럼 맨앞에 10은 고정이다.

10을 고정하고 뒤에 수를 보자.

N = 3일때 까지는 사실상 규칙이 없어서 코드에 dp[3]까지 정의해줬어야 하는데, 어차피 답나와서 그냥 싸잡아서 for문에 넣었다.

 

N = 4

10 00

10 01

10 10

00과 01은 N = 3에서, 10은 N = 2에서와 연속된다.

 

N = 5

10 000

10 001

10 010

10 100

10 101

000과 001, 010은 N = 4에서, 100과 101은 N=3에서 가져온것이다.

 

가져오는 수들이 왜 뒤에서부터 가져오는거냐고 물으면 규칙이 그렇게 나온다.

 

후기 : 그냥 규칙 찾아보려고 수를 쭉나열했는데 답을 찾았다.피보나치같네

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: 91)
dp[1] = 1
dp[2] = 1
for i in stride(from: 3, through: n, by: 1){
    dp[i] = dp[i - 1] + dp[i - 2]
}
print(dp[n])