[동적계획법, 난이도 중하] 백준 2579번 계단 오르기

이 문제의 주어진 조건을 요약하자면, 계단을 3칸 연속으로 밟을 수 없고 마지막 칸은 무조건 밟아야 한다는 것이다.

 

배열 save를 n번째 계단까지 올랐을 때 얻을 수 있는 최대 점수, 배열 floors을 초기 입력된 계단 점수 배열이라 하면

이 문제의 점화식은 이렇게 된다.

save[i] = maxs((save[i - 3] + floors[i - 1] + floors[i]), (save[i - 2] + floors[i])); 이다.

 

왜 이런 식이 나오는지는 아래 그림과 같이 설명하겠다.

위 그림에서 연한 노란색은 이미 DP로 처리한 부분이고

진한 노란색은 밟을 수 있는 계단들이다.

즉, 계단을 연속 3칸으로 밟는 것을 피하기 위해선 위와 같은 그림의 (O) 케이스가 되어야 하는데

3번째 케이스는 왜 계산하지 않냐면, N-2, N-1번째 계단을 이미 밟은 상태라면 N번째 계단은 밟지 못하기 때문이다.

 

이러한 원리로 위와 같은 점화식을 세울 수 있다.

만약 N=1 또는 N=2 라면 모든 계단을 밟았을 때가 최대 점수이기 때문에 save[1], save[2]는 미리 설정해두고 save의 세 번째 인덱스부터 DP를 수행하면 된다.  

 

 

#include <iostream>
#define max(x,y) (x>y)? x:y
using namespace std;
int save[301];
using namespace std;
int maxs(int x, int y) {
	if (x >= y) return x;
	else return y;
}
int main() {
	int floor;
	cin >> floor;
	int *floors = new int[floor + 1];
	for (int i = 1; i < floor + 1; i++) {
		cin >> floors[i];
	}
	save[1] = floors[1];
	save[2] = save[1] + floors[2];
	for (int i = 3; i < floor + 1; i++) {
		save[i] = maxs((save[i - 3] + floors[i - 1] + floors[i]), (save[i - 2] + floors[i]));
	}
	cout << save[floor];
}

 

 

+) 2021-10-03 백준 숏코딩 상위 0.24% 파이썬 코드

e=[0]
d=[0]
n=int(input())
for _ in range(n):e.append(int(input()))
d.append(e[1])
if n>1:d.append(e[1]+e[2])
for i in range(3,n+1):d.append(max(d[i-3]+e[i-1]+e[i],d[i-2]+e[i]))
print(d[n])