백준 2579 계단 오르기

문제링크 : https://www.acmicpc.net/problem/2579

아이디어

• 이전에 계산한 값을 재활용 할 수 있음 > DP
  • 각 조건이 복잡하니까 2차원 DP로
  • DP[Y][X] : Y위치에서 X가 0이면, 이전에 한칸으로 온 경우, 1이면 이전에 2칸으로 온 경우
  • DP[Y][0] = DP[Y-1][1]
  • DP[Y][1] = max(DP[Y-2][0], DP[Y-2][1])
• 초기값 설정
  • DP[1][0] = map[1]
  • DP[1][1] = 0
  • DP[2][0] = map[1] + map[2]
  • DP[2][1] = map[2];
    • DP[N][0], DP[N][1] 중 큰값 출력

시간복잡도 계산

• O(N * 2)

자료구조

• map[Y] : 계단 최대 1e4 > INT 가능
• DP[Y][X] :
  • 최대값 : 1e4 * 300 = 3e6 > INT 가능

코드(C++)

#include <iostream>
 
using namespace std;
 
int map[310];
int dp[310][2];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0], &dp[309][2], 0);
    int N; cin >> N;
    for(int i=1; i<=N; i++) cin >> map[i];
    
    dp[1][0] = map[1];
    dp[1][1] = 0;
    
    dp[2][0] = map[1] + map[2];
    dp[2][1] = map[2];
    
    
    for(int i=3; i<=N; i++) {
        dp[i][0] = dp[i-1][1] + map[i];
        dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + map[i];
    }
    
    cout << max(dp[N][0], dp[N][1]) << '\n';
    
    return 0;
}
 

문제유형

• 케이스 2차원 DP : 조건이 복잡할 때, 각 케이스에서의 dp

비슷한 문제

• https://www.acmicpc.net/problem/2579
• https://www.acmicpc.net/problem/1309
• https://www.acmicpc.net/problem/2169