백준 2579번 계단 오르기 - SWIFT

문제

---

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

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

 
<그림 2>
계단 오르는 데는 다음과 같은 규칙이 있다.

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
 

입력

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

출력

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

문제 링크

https://www.acmicpc.net/problem/2579
 
 

풀이

---

다이나믹 프로그래밍을 활용해야하는 문제다.
이 문제의 경우 초점을 어떻게 잡아야좋을까 고민을 많이 했다.
(사실 여러 번 틀린 이유는 인덱스 에러를 못잡아서이다...)
고민 끝에 나온 결론은 현재 계단에 초점을 두는 것이었다.
 

프로그램 동작

일단 dp table은 아래와 같이 의미를 두어 만들었다.
0번 행의 의미는 연속해서 두 계단을 밟았다는 것, 즉 직전 계단과 현재 계단을 밟았다는 것이다.
1번 행의 의미는 한 계단을 건너뛰고 밟았다는 것, 즉 두칸 전 계단과 현재 계단을 밟았다는 것이다.
dp table의 각 값이 의미하는 바는 현재 계단까지 밟았을 때 얻을 수 있는 최대 값을 말한다.
결국 직전 최댓값을 활용해 현재 최댓값을 얻겠다는 말이다.▼

 
dp table을 설정했다면 첫번째 부터 값을 넣어주기 시작한다.
맨 처음 계단을 밟는 다고 했을 때는 그 이전 계단이 없으므로, 맨 처음 계단 값이 최댓값이다.▼

 
하지만 두번째 계단부터는 값이 다르게 들어간다.
연속 밟기를 했을 경우, 연속 밟기를 했다는 거 자체가 최댓값이라 바로 값을 넣어주면 된다.

하지만 문제조건 중에 연속된 세 개의 계단을 모두 밟아서는 안 된다. 라는 조건이 있기 때문에

연속 밟기를 하지 않았던 1번 행의 값을 끌어와 사용한다.
만약 연속 밟기를 한 0번 행의 값을 끌어와 사용한다면, 연속해서 세 계단을 밟는게 되므로 문제 조건에 어긋난다.
연속 밟기를 하지 않을 경우, 첫번째 계단 외의 계단이 없으므로 현재 값만 넣어준다.▼

 
세번째 계단부터 본격적으로 반복하는 과정이 들어간다.
연속 밟기를 했을 경우, 앞에서와 마찬가지로 1번 행의 값을 끌어와 사용한다.
연속 밟기를 하지 않을 경우, 이제부터 최댓값을 골라 더하는 행위를 한다.
두 칸 전의 계단에서, 연속 밟기를 한 값이 더 크다면 연속 밟기를 한 값을 끌어오고,
연속 밟기를 하지 않은 값이 더 크다면 연속 밟기를 하지 않은 값을 끌어오면 된다.
두 칸 전의 계단을 밟고 현재 계단을 밟는다는 것은 애초에 연속으로 계단을 밟는다는 것이 아니므로 연속 밟기를 했던 값과 연속 밟기를 하지 않은 값 둘 다 올 수 있다.▼

 
이제부터 세번째 계단에서 했던 과정을 반복해주면 된다.
마지막 계단은 꼭 밟아야 한다고 했으므로, 마지막 계단 까지 dp table을 채워주면 된다.▼

 
 
다 채워줬다면, dp table의 마지막 열의 값 중 큰 값이 답이 된다.
 

Swift 코드

---

let N = Int(readLine()!)!
var arr = [Int]()
var cache : [[Int]] = Array(repeating: Array(repeating: 1, count: 2), count: 301)

for _ in 1...N {
    let a = Int(readLine()!)!
    arr.append(a)
}
cache[0][1] = arr[0]
cache[0][0] = arr[0]
if N > 1 {
    cache[1][1] = arr[1]
    cache[1][0] = arr[0] + arr[1]
    if N > 2 {
        for i in 3...N {
            cache[i - 1][0] = cache[i - 2][1] + arr[i - 1]
            cache[i - 1][1] = max(cache[i - 3][0], cache[i - 3][1]) + arr[i - 1]
        }
    }
}

print(max(cache[N - 1][0], cache[N - 1][1]))