Jenikeju

내가 푼 풀이

- 길이 n의 계단 수를 구한다( 각 자리수의 차이가 1)

- i: 길이, j: 마지막자리의 숫자로 dp[i][j] 는 길이가 i인 마지막숫자 j가 오는 계단수의 갯수로 정의한다.

- dp[1][j] = 1 (  0 < j < 10 )

- 마지막자리 숫자가 0 인경우, 앞자리 수는 반드시 1 이와야하고, 마지막자리가 9라면, 앞자리 수는 반드시 8이어야 계단수가 성립한다.

- 나머지의 경우 는 마지막자리수 j의 앞자리수는 j-1 , j+1 이 될 수 있다.

- 이를 점화식으로 표현하면

• if j == 0 , dp[i][0] = dp[i-1][1]
• if j == 9 , dp[i][9] = dp[i-1][8]
• dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

- dp값을 넣어줄때 항상 10억으로 나눠주고, 결과도 10억으로 나눠서 출력한다.

import Foundation

let num = Int(String(readLine()!))!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: num+1)

for i in 1...9 {
    dp[1][i] = 1
}

if num == 1 {
    print(dp[num].reduce(0, +))
} else {
    for i in 2...num {
        for j in 0...9 {
            if j == 0 {
                dp[i][j] = dp[i-1][1] % 1000000000
            } else if j == 9 {
                dp[i][j] = dp[i-1][8] % 1000000000
            } else {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000
            }
        }
    }
    
    print(dp[num].reduce(0, +) % 1000000000)
}

내가 푼 풀이

- 이 문제는 2579번 계단오르기 문제와 유사하다.

- 연속된 3개의 잔은 먹을수 없다.

- 계단오르기문제와 차이점은 계단은 n번째 계단을 올라가야 그 이후 계단을 오를수있지만, 포도주는 아예 안먹을 수 있다.

- 첫번째와 두번째 포도주까지는 무조건 먹는것이 포도주의양 최댓값이다.

- 1번째 포도주: dp[1] = arr[1], 2번째 포도주: dp[2] = arr[1] + arr[2]

- 세번째부터 i번째까지, i번째 포도주를 먹는경우: max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])

- dp[i] 를 먹는경우로 저장하고 이제 먹지않는 경우를 비교한다. dp[i] = max(dp[i-1], dp[i])

- dp[i-1]와 dp[i] 를 비교한 이유는 dp[i-1]은 i-1번째 포도주를 마신경우의 최댓값이다.

- 여기서 i-1, i-2 를 연달아 마신경우, i-3 i-1로 마신경우 모두 포함하므로 dp[i-1] 과 비교하였다.

import Foundation

let count = Int(String(readLine()!))!
var dp = Array(repeating: 0, count: count+1)
var arr = [0]
dp[0] = 0
for i in 0..<count {
    arr.append(Int(String(readLine()!))!)
}

dp[1] = arr[1]
if count != 1 {
    dp[2] = arr[1] + arr[2]
    if count > 2 {
        for i in 3...count {
            dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
            dp[i] = max(dp[i-1], dp[i])
        }
    }
}
print(dp.max()!)

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

내가 푼 풀이

- P(1) = 1, P(2) = 1, P(3) = 1, P(n) = P(n-2) + P(n-3) 임을 알수있다. (n > 3) 

- 해당 점화식을 넣어서 P(N)값 출력

import Foundation

let count = Int(String(readLine()!))!

for i in 0..<count {
    let num = Int(String(readLine()!))!
    var dp = Array(repeating: 0, count: num+1)
    
    if num <= 3 {
        dp[num] = 1
        print(dp[num])
    } else {
        for i in 1...num {
            if i <= 3 {
                dp[i] = 1
                continue
            }
            dp[i] = dp[i-2] + dp[i-3]
        }
        print(dp[num])
    }

}