[백준] 계단오르기 2579 c++

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

2579번: 계단 오르기

 

[규칙]

1. 계단은 한 번에 한 칸 or 두 칸

2. 연속 세 칸  X

3. 마지막 도착 계단은 반드시 밟아야 함

4. 총 점수의 최댓값 구하기

 

[실패 원인]

1. DFS로 푸는 게 젤 안전할 것 같아서 풀었는데 시간 초과가 나왔다. 

- 아마 제한시간이 1초여서 계단의 수가 300 이하이지만, 시간이 부족한 것 같았다. 

2. DFS 말고 아래 설명할 알고리즘으로 풀었는데, 세번째 칸이 무조건 (첫 번째 계단 + 세 번째 계단) 값인 줄 알았는데 문제를 잘 보니 

이렇게 시작점은 포함되지 않기 때문에,(첫 번째 계단 + 세 번째 계단) OR(두 번째 계단 최댓값 + 세 번째 계단)의 최댓값이 세 번째 계단 값이었다. 

 

[풀이 설명]

DFS가 실패한 뒤, 실패한 이유는 시간 초과여서 '그럼 반복하여 배열을 이용해서 해보자'라는 생각을 하게 되었다. 

순서대로 생각을 해보면, 

 

º 첫 번째 계단은 1번째 계단 값

º 두 번째 계단은 1번째 계단 + 2번째 계단

º 세 번째 계단은

    (1번째 계단 + 3번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 3번째 계단) : 시작점은 연속된 세 개의 계단을 밟아서는 안된다는 조건에 빠지기 때문

º 네 번째 계단은

    (1번째 계단 + 3번째 계단 + 4번째 계단) 

            OR

    (1번째 계단 + 2번째 계단+ 4번째 계단)

º 다섯 번째 계단은

    (2번째 계단 + 4번째 계단 + 5번째 계단) 

            OR

    (3번째 계단+ 5번째 계단) 

이렇게 된다.

 

 

그래서 식을 생각해보면

X자리의 최댓값을 구하려면

X자리 계단 값 + X-2의 최댓값

X자리 계단 값 + X-1의 계단 값 + X-3의 최댓값

이라는 식이 나온다.

 

그렇지만 X-1은 왜 계단 값을 구하냐

이것은 옆의 판을 보면 알 수 있다. 

5번의 계단의 최댓값을 구할 시

2번, 4번, 5번 이렇게 뛰어넘는다고 생각하면

4번째 계단은 무조건 앞에 3번을 포함하지 않아야 한다. 

4번째 계단의 최댓값을 구한다면, 3번이 포함할 수 있기 때문에 사용하지 않는다. 

 

 

이렇게 소스코드를 짜면,

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


int main() {
	int N;
	int score[301];
	int max_score[301];

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> score[i + 1];

	max_score[1] = score[1];
	max_score[2] = score[1] + score[2];
	max_score[3] = max(score[2]+score[3],score[1] + score[3]);

	for (int i = 4; i <= N; i++) {
		max_score[i] = max(score[i] + max_score[i - 2], max_score[i - 3] + score[i - 1] + score[i]);
	}
	cout << max_score[N];
	return 0;
}

 

나온다.