백준 2579번(S3) - 계단 오르기 풀이정리

백준 2579번 : 계단 오르기

---

---

풀이 과정

---

DP문제로 실버3짜리인데 개인적으로 너무 힘든 문제였음.

DP라면 점화식을 짜서 풀어야하는데.. 머리가 안돌아가서 점화식을 짜기가 너무 힘들어서 조금씩 게시판을 봐가면서 풀었음..

처음 생각한 것은 계단 끝에서부터 시작해서 전 계단과 2칸 전 계단과 비교하여 큰 값을 dp 배열에 담아서 계산하였음.

하지만 이렇게 하는 것은 그리디 알고리즘이었음..

그 다음 생각한 것은 step을 함수 인자로 줘서 재귀로 값을 구하는 방식이었음. 우선 알고리즘은 다음과 같음.

마지막 계단은 무조건 밟아야 하므로 마지막 계단 전 계단을 밟았을 때와 2칸 전의 계단을 밟았을 때로 구분하여 시도하였음.

dp[n] = n번째 계단을 밟았을 때 최대값이라고 하면 dp[n] = max( f(n-1,1) , f(n-2,2) ) + s[n]로 점화식을 세웠음.

step은 0, 1, 2로 구분하였음.

• 0은 문제에서 요구하는 값

• 1은 n번째 계단에서 한 칸 뺀 n-1번째 계단

• 2는 n번째 계단에서 두 칸 뺀 n-2번째 계단으로 하였음.

  • step = 1이면, 2칸 연속으로 계단을 오른 것이므로 무조건 2칸 뒤에 있는 계단으로 가줘야 함.

  • step = 2이면, 1칸 뒤 계단과 2칸 뒤 계단까지 올랐을 때를 비교하여 더 큰 값에 현재 계단의 점수를 더해야 함.

따라서 최종 코드는 아래와 같이 나왔음.

#include <iostream>
#include <algorithm>
using namespace std;

int stairs[301] = {0,};     /* stairs[1] = 1번째 계단 */
int dp[301] = {0,};         /* dp[i] = i번째 계단을 올랐을 때의 최대값 */

int f(int n, int step) {
    if (n == 0 or n == 1) { return dp[n]; }
    if (step == 1) 
    {
        return dp[n] = f(n - 2, 2) + stairs[n];
    } 
    else 
    {
        return dp[n] = max(f(n - 1, 1), f(n - 2, 2)) + stairs[n];
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) { cin >> stairs[i]; }

    dp[1] = stairs[1];
    cout << f(n, 0) << '\n';
    return 0;
}

재귀식을 돌리면 아래처럼 계산을 하게 됨.

n=6

f(6,0) -> dp[6]=max(f(5,1), f(4,2)) + s[6] // 55 + 20 = 75

f(5,1) -> dp[5] = f(3,2)+s[5] // 35 + 10 = 45

f(4,2) -> dp[4] = max(f(3,1), f(2,2)) + s[4] // 30 + 25 = 55 

f(3,2) -> dp[3] = max(f(2,1), f(1,2)) + s[3] // 20 + 15 = 35

f(3,1) -> dp[3] = f(1,2) + s[3] // 10+15 = 25

f(2,2) -> dp[2] = max( f(1,1), f(0,2) ) + s[2] // 10+20 = 30

f(2,1) -> dp[2] = f(0,2)+s[2] // 20

f(1,2) -> dp[1] = s[1] // 10

f(1,1) -> dp[1] = s[1] // 10

f(0,2) -> dp[0] = 0

n=3  --> 1, 2, 3

f(3,0) -> dp[3] = max( f(2,1), f(1,2) ) + s[3] // 2 + 3 = 5

f(2,1) -> dp[2] = f(0,2) + s[2] = s[2]  // 0 + 2 = 2

f(1,2) -> dp[1] = s[1] // 1

이 코드의 문제점은 바로 n의 값임.

n 값이 너무 크면 재귀함수의 속도가 너무 오래 걸리므로 시간초과가 발생하게 됨..

질문 게시판에 시간초과 관련 글을 보면 답변에 링크가 하나 있음.

네임드유저가 DP 강의를 한 게시글인데 이걸 보고 내 코드를 토대로 2차원 배열로 풀어보기로 함.

blog.encrypted.gg/974

기존 알고리즘 그대로 2차원 배열로 step을 추가해줬음.

dp[i][0] : max(dp[i-1][1], dp[i-2][2])

dp[i][1] -> i+1에서 1칸 뺀 거

dp[i][2] -> i+1에서 2칸 뺀 거

---

최종 풀이

---

#include <iostream>
#include <algorithm>
using namespace std;
// typedef unsigned long long int uli;

int s[301] = {0,}; 
int dp[301][3];	  

/*
dp[i][0] : max(dp[i-1][1], dp[i-2][2])
dp[i][1] -> i+1에서 1칸 뺀 거
dp[i][2] -> i+1에서 2칸 뺀 거
*/

/*
int f(int n, int step) 
{
	if(n == 0 or n == 1) { return dp[n]; }
	if(step == 1) 
	{
		return dp[n]=f(n-2,2)+s[n];
	}
	else 
	{
		return dp[n]=max(f(n-1,1), f(n-2,2))+s[n];
	}	
}
*/

int main() 
{
    ios::sync_with_stdio(false); 
    cin.tie(NULL);

    int n; cin >> n;
    for(int i=1; i<=n; i++) { cin >> s[i]; }
	
    dp[1][0]=s[1], dp[1][1]=s[1], dp[1][2]=s[1];
	
    for(int i=2; i<n; i++)
    {
        dp[i][1]=dp[i-2][2]+s[i];
        dp[i][2]=max(dp[i-1][1], dp[i-2][2])+s[i];
        dp[i][0]=max(dp[i-1][1], dp[i-2][2])+s[i];
    }
    dp[n][0]=max(dp[n-1][1], dp[n-2][2])+s[n];
	
    cout << dp[n][0] << '\n';
    return 0;
}

---