[C/C++] 코드업(codeup) 4564번 계단 오르기

▽문제 바로가기

https://codeup.kr/problem.php?id=4564

계단 오르기

---

입력

첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다.

계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10000이하의 자연수이다.

 

출력

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

 

문제 풀이

 

규칙

1. 계단은 한 번에 한게단씩 또는 두 계단씩 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟지 못한다.

3. 마지막 계단은 반드시 밟아야 한다.

 

계단은 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10000이하의 자연수이다.

 

규칙을 먼저 찾아봅시다. 계단의 점수를 stairs[i]에 저장했다고 하면

 

1계단은

1계단

 

2계단은

1계단-1계단

2계단

 

3계단은

1계단-1계단-1계단

1계단-2계단

2계단-1계단

 

연속된 세 개의 계단을 밟을 수 없으므로 두 가지의 경우의 수가 존재합니다.

마지막으로, 하나만 더 해봅시다.

 

4계단은

1계단-1계단-1계단-1계단

2계단-1계단-1계단

1계단-2계단-1계단

1계단-1계단-2계단

2계단-2계단

 

마찬가지로 연속된 세 개의 계단을 밟을 수 없으므로 세 가지의 경우의 수가 존재합니다.

이렇게 경우의 수를 구하다 보니 특징 두 가지가 존재합니다.

 

1. n-1계단을 밟으면 n-2계단은 밟지 못합니다. n-3계단을 밟아야 합니다.

f(n) = f(n-3) + stairs[n-1] + stairs[n]

 

2. n-1계단을 밟지 않으면 n-2계단을 무조건 밟습니다.

f(n) = f(n-2) + stairs[n]

 

단, f(n-3)과 f(n-2)는 지금까지 해당 계단을 오르는 경우의 수들의 값 중 가장 큰 값이어야 합니다.

 

#include <stdio.h>

int memo[301]={0};	//메모 
int stairs[301] ={0};	//계단값 저장

int mymax(int a, int b){
	return a>b? a:b;
}

int recur(int a){
	if(a<0) return 0;
	if(a==1) return memo[1] = stairs[1];
	if(a==2) return memo[2] = stairs[1] + stairs[2];
	if(memo[a]!=0) return memo[a];
	else return memo[a] = mymax(recur(a-3)+stairs[a-1], recur(a-2))+stairs[a];
}

int main(){
	
	int a, b;
	scanf("%d", &a);
	for(int i=1;i<a+1;++i){
		scanf("%d", &stairs[i]);
	}
	
	printf("%d\n", recur(a));
	
	return 0;
}