[Swift][DP] 백준 1303번 (동물원)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

 

2xn의 사각형이 있을때, 사자가 가로, 세로방향으로 있으면 안된다.

사자가 있을 수 있는 경우의수는 왼쪽, 오른쪽, 그리고 아예없을 경우이다.

이 문제는 사자를 배치하는 모든 경우의수를 구하는 문제이다.

 

점화식을 만들어보자.

dp[i]를 구하려는데 i번째 배열에는 사자가 없을 수도 있다.

사자가 없는경우에는 이전 인덱스인 i - 1에서는 왼쪽에 사자가 있을 수도 있고 오른쪽에 사자가 없을 수도 있고 사자가 아예 없을 수도 있다.

이 문제는 사자를 배치할 수 있는 모든 경우의수를 구하는 것이므로,

조건별로 경우의수를 다 구해준다.

각각 다른 조건을 만족하는 경우의수들을 구하기 위해서는 dp를 2차원 배열로 사용해야한다.

dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][0]) % 9901 //사자가 없는경우
dp[i][1] = (dp[i - 1][2] + dp[i - 1][0]) % 9901 //사자가 왼쪽에 있는 경우
dp[i][2] = (dp[i - 1][1] + dp[i - 1][0])  % 9901 //사자가 오른쪽에 있는 경우

나는 dp[i]에 사자가없는경우는 dp[i][0]으로, 왼쪽에 있는경우는 dp[i][1]로, 오른쪽에 있는 경우는 dp[i][2]로 구분해 두었다.

 

혹시나, 이해가 안가는 사람들을 위해 좀 더 설명해보면

dp[i][0]을 보자.

dp[i][0]의 경우 dp[i]에 사자가 없는 경우이다.

사자가 없다는것은 dp[i - 1]에 왼쪽에도 사자가 올 수 있고, 오른쪽에도 올 수 있고, 안올 수도 있다.

우리는 모든경우의수를 구하기 때문에 왼쪽에오는거(dp[i - 1][1]) + 오른쪽에오는거(dp[i - 1][2]) + 안오는거(dp[i - 1][0])을 다 더해준것이다.

 

참고 : 프린트하는 부분에도 % 9901 안해주면 "틀렸습니다."가 나올것이다.

 

후기 : 이전에 푼 RGB거리와 유사한 이차원 배열을 활용해서 조건의 경우의수를 따져주는 문제이다.

연속으로 풀게되어있는 문제집이 참 좋은것같다.

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