[백준(BOJ)] 2579 계단 오르기 - 스위프트(Swift)

[Silver III] 계단 오르기 - 2579

문제 링크

성능 요약

메모리: 69100 KB, 시간: 8 ms

분류

다이나믹 프로그래밍

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

풀이

해당 문제는 동적 계획법(Dynamic Programming)인 DP로 문제를 해결해야 합니다.

 

3번 조건인 "마지막 도착 계단은 반드시 밟아야 한다"는 조건을 생각하여 마지막 계단을 기준으로 생각해보았습니다.

1,2번 조건 또한 만족하는 경우를 따져보면, 마지막 계단의 이전 계단을 밟았는 지를 생각해보아야 합니다.

 

마지막 계단이 i번째라고 가정한다면,

i - 1 번째 계단을 밟았을 때는 i - 2 번째 계단을 밟으면 안되고, 처음부터 i - 3 번째까지의 최댓값이 정답일 것입니다.

i - 1 번째 계단을 밟지 않았을 때는 처음부터 i - 2 번째까지의 최댓값이 정답이 될 것 입니다.

 

따라서 위의 두 가지 경우 중 최대값을 선택하는 것이 i번째의 최대값이기 때문에, 다음과 같이 코드를 작성할 수 있습니다.

dp[i] = max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i])
// 첫 번째 경우와 두 번째 경우

 

이것을 기반으로, 전체 코드를 작성해보았습니다.

 

let n = Int(readLine()!)!
var (stair, dp) = ([Int](), Array(repeating: 0, count: n))

for _ in 0..<n {
    stair.append(Int(readLine()!)!)
}
(dp[0], dp[1], dp[2]) = (stair[0], stair[0] + stair[1], max(stair[0] + stair[1], stair[1] + stair[2], stair[0] + stair[2]))


if n <= 3 {  // 3개 이하일 때
    print(dp[n - 1])
} else {    // 4개 이상일 때 -> index of out range
    for i in 3..<n {
        dp[i] = max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i])
    }
    print(dp[n])
}

→ 런타임 에러

 

스위프트 같은 경우에는 UpperBound와 LowerBound를 신경써줘야 하기 때문에 해당 에러가 나타났습니다.

 

따라서 처음 3개까지의 값을 먼저 정해주지 말고, 각각의 케이스에 맞춰서 dp 배열의 값을 생성해야 합니다.

 

예를 들어 n이 1이라면 계단은 2개보다 적은데, dp[2]를 구하기 위해선 계단의 두 번째 값을 알아야 하기 때문에 런타임 에러가 발생하였습니다.

 

따라서 다음은 위의 케이스를 반영한 코드입니다.

let n = Int(readLine()!)!
var (stair, dp) = ([Int](), Array(repeating: 0, count: n))

for _ in 0..<n {
    stair.append(Int(readLine()!)!)
}


if n == 1 {
    print(stair[0])
} else if n == 2 {
    print(stair[0] + stair[1])
} else if n == 3 {
    print(max(stair[0] + stair[1], stair[1] + stair[2], stair[0] + stair[2]))
} else {    // 4개 이상일 때 -> index of out range
    dp[0] = stair[0]
    dp[1] = stair[0] + stair[1]
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])
    for i in 3..<n {
        dp[i] = max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i])
    }
    print(dp[n - 1])
}

 

 

 

DP를 생각할 때에는 조건들을 유심히 살펴보고, 해당 조건에 부합하는 일반적인 식을 어떻게 도출할 수 있을 지 고민하는 것이 매우 중요한 것 같습니다.