문제링크
https://www.acmicpc.net/problem/2579
문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에 계단의 개수가 주어진다.
둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 128MB
해설
계단을 오르면서 점수를 쌓아간다. 가장 윗 계단을 밟았을 때 받을 수 있는 가장 큰 점수를 출력하면 된다. 2번 조건에 의해 1칸씩 움직이는 것을 연속 2번 할 수는 없다. 즉, 2칸 움직이기 / 2칸 움직이고 1칸 움직이기 2가지 계단을 오르는 방법을 이용해야 하며, 둘 중 더 큰 점수를 얻을 수 있는 움직임을 선택하면 된다. 마지막 계단 뿐만 아니라, 중간에 있는 계단에서도 가장 큰 점수를 얻었을 때 최종 점수가 가장 커질 수 있으므로, 작은 문제로 나누어 해결하면 된다. → 다이나믹 프로그래밍
풀이
계단의 각 점수를 나타내기 위한 stair 벡터와 계단까지의 최대 점수를 나타내기 위한 score 벡터를 따로 사용하였다. score 벡터는 모든 원소의 값을 0으로 선언과 동시에 초기화해준다. 두 벡터의 크기는 n+1로 하여, n번째 계단이 index n에 위치할 수 있게 해주었다. (편의와 가독성을 위해)
연속해서 2번 1칸 움직이는 것을 방지하기 위해, 움직임의 종류는 2칸 움직이기 / 2칸 움직이고 1칸 움직이기 총 2 종류를 사용한다. k번째 계단의 최대 점수를 구하고자 한다고 해보자. 2칸을 움직이는 경우에는 k-2칸 까지의 최대 점수 + k번째 계단의 점수 / k-3칸 까지의 최대 점수 + k-1번째 계단의 점수 + k번째 계단의 점수 중 큰 값을 k번째 계단의 점수로 갖는다. 이를 코드로 나타내면 아래와 같다.
score[k] = max(stair[k]+score[k-2], stair[k]+stair[k-1]+score[k-3]);이를 이용해 n번째 계단까지 이미 구한 계단들의 score 값을 이용해 점수를 구하는 반복문을 작성하면 아래와 같다.
// 1번째 계단부터 n번째 계단까지
for(int k = 1; k < n+1; k++) {
score[k] = max(stair[k]+score[k-2], stair[k]+stair[k-1]+score[k-3]);
}여기에서 score[k-3]에 접근하기 때문에 OutOfBound 에러가 발생한다. k가 2보다 작거나 같을 때는 우리가 미리 정의한 움직임의 형태를 사용하지 못하기 때문에 수동으로 값을 넣어주어야 한다. 1번째 계단은 그냥 1칸 이동하기 / 2번째 계단은 2칸을 한 번에 이동하거나 1칸씩 두 번 이동하는 방법밖에 없다. 2번째 계단의 경우, 둘 중 최대 점수를 얻을 수 있는 방법을 선택하면 된다. 위 사항을 반영하면 코드를 아래처럼 수정해주어야 한다.
for(int k = 1; k < n+1; k++) {
if(k>2) {
score[k] = max(stair[k]+score[k-2], stair[k]+stair[k-1]+score[k-3]);
} else {
if (k == 1) {
score[k] = stair[k];
} else {
score[k] = max(stair[k]+score[k-1], stair[k]+score[k-2]);
}
}
}위 반복문을 지나고 나면 구하고자 하는 n번째 계단의 최종 최대 점수는 score[n]에 저장되어 있다. 이 값을 출력하면 된다.
코멘트
문제를 잘 읽자... 나는 왜 1칸 이동 연속 2번이 안되는지 이해를 못하고 있었다... 나는 빡빡이다...
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
int n;
cin >> n;
vector<int> stair(n+1);
stair[0] = 0;
for(int k = 1; k < n+1; k++) {
cin >> stair[k];
}
vector<int> score(n+1, 0);
for(int k = 1; k < n+1; k++) {
if(k>2) {
score[k] = max(stair[k]+score[k-2], stair[k]+stair[k-1]+score[k-3]);
} else {
if (k == 1) {
score[k] = stair[k];
} else {
score[k] = max(stair[k]+score[k-1], stair[k]+score[k-2]);
}
}
}
cout << score[n];
return 0;
}
Uploaded by Notion2Tistory v1.1.0