계단 오르기

오늘의 문제

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

계단 오르기

문제 분석

• 입력은 10000까지에 300가지이므로 int자료형으로 충분하고, 시간도 넉넉하다.
• 앞의 결과가 다음에 영향을 미치는 경우이므로, DP를 사용한다. 1칸을 3번이상 갈 수 없는 제한없이 맨 위까지 갈 수 있는 경우의 수라면, 이것도 피보나치가 될 수 있다.
• 1칸으로 올라온 결과와 2칸으로 올라온 결과를 저장한다. 1칸으로 올라온 결과를 저장할 때, 앞의 결과에서 2칸으로 올라온 결과만 채택한다.

나의 풀이

#include <iostream>
using namespace std;
int n;
const int MAX = 300;
int score[MAX];

// 계단 오르기
int solution(){
    int t_score[MAX][2] = {0, }; // 한번, 두번으로 올라온것
    t_score[0][0] = score[0];
    t_score[1][0] = score[0] + score[1];
    t_score[1][1] = score[1];
    for(int i=2;i<n;i++){
        t_score[i][0] = t_score[i-1][1] + score[i];
        t_score[i][1] = max(t_score[i-2][0], t_score[i-2][1]) + score[i];
    }
    
    return max(t_score[n-1][0], t_score[n-1][1]);
}

다른 풀이

#include<stdio.h>

int ar[302];
int D[302];

int main(){

	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&ar[i]);
		D[i]=D[i-3]+ar[i-1]>D[i-2]?D[i-3]+ar[i-1]+ar[i]:D[i-2]+ar[i];
	}
	printf("%d",D[n]);
	return 0;
}

배울 점

• 한줄로 잘 축약한다. DP로 푼다는 근본은 같다.