알고리즘 문제(Swift) - 백준 - 2579 (계단 오르기)

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

 

 

1. 문제의 재귀적인 구조 파악
   • 마지막 계단은 무조건 밟아야 됨 → Top - Down 이용
   • 계단은 한 칸 또는 두 칸 이동 가능
     • f(i, 1) (연속된 계단이 1개일 때) = max(f(i + 1, 2), f(i + 2, 1)) + score[i]
     • f(i, 2) (연속된 계단이 2개일 때) = f(i + 2, 1) + score[i]
   • 연속된 세 개의 계단을 밟으면 안 됨
2. 수식으로 표현
   • f(i) = max(f(i - 1), f(i - 2)) + score[i]
   • 연속된 계단의 개수 표현
3. 초기값 처리 (기저 조건)
   • 마지막 계단은 밟아야 되기 때문에, 넘어가는 계단은 Int.min으로 최소값 처리
   • 마지막 계단을 밟았을 때 얻었을 수 있는 최대 점수는 score[n]

 

첫 번째 시도: 재귀함수 이용

• count: 해당 계단을 밟았을 때 연속된 계단의 개수

let n = Int(readLine()!)!
var dp = Array(repeating: 0, count: n + 1) // 각 계단을 밟았을 때, 얻을 수 있는 최대 점수 저장
var score = [0] // 점수 배열
for _ in 0..<n {
    score.append(Int(readLine()!)!)
}
dp[n] = score[n] // 마지막 계단을 밟았을 때 얻었을 수 있는 점수는 최대 score[n]
        
func recur(_ i: Int, count: Int) -> Int {
    if i == n { // 마지막 계단을 밟았으면 마지막 칸 점수 리턴
        return dp[n]
    }
    if i > n { // 마지막 계단을 밟지 않았다면, 최소 값 처리
        return Int.min
    }
    
    if count > 1 { // 연속된 계단이 2개라면 다음 칸은 무조건 2칸 전진 해야 함
        dp[i] = recur(i + 2, count: 1) + score[i]
    } else { // 연속된 계단이 1개라면 1칸을 가도 되고, 2칸을 가도 됨
        dp[i] = max(recur(i + 1, count: count + 1), recur(i + 2, count: 1)) + score[i]
    }
    return dp[i]
    
}

print(recur(0, count: 0))

→ 시간초과

메모이제이션을 사용하지 않아서 효율성이 떨어짐

 

두 번째 시도: Top - Down 방식

• 마지막 칸을 지나치면 최소값 처리를 위해 dp의 길이 n + 2 사용
• 각 계단마다 연속으로 밟은 계단의 수에 따라 다른 값이 나오므로 2차원 배열 사용

let n = Int(readLine()!)!
// 마지막 칸을 지나치면 최소값 처리를 위해 n + 2 사용
// 각 계단과 연속으로 밟은 계단을 따로 처리하기 위해 2차원 배열 사용
var dp = Array(repeating: Array(repeating: 0, count: 3), count: n + 2)
var score = [0] // 점수 배열
for _ in 0..<n {
    score.append(Int(readLine()!)!)
}
// 초기값 설정
dp[n] = [0, score[n], score[n]]  // 마지막 계단은 모두 score[n]
dp[n + 1] = [0, Int.min, Int.min] // 마지막 계단 이후는 최소값 처리

// 마지막 계단 한 칸 아래부터 시작
for i in stride(from: n - 1, through: 0, by: -1) {
    // 연속된 계단이 1개일 경우 1칸을 가도 되고 2칸을 가도 됨
    dp[i][1] = max(dp[i + 1][2], dp[i + 2][1]) + score[i]
    // 연속된 계단이 2개일 경우 반드시 2칸을 감
    dp[i][2] = dp[i + 2][1] + score[i]
}
print(dp.flatMap{$0}.max() ?? 0) // 최대값 출력

→ 맞았습니다!