알고리즘 스터디 5회차 - 동적 계획법 (백준 2579번: 계단 오르기)

이번 알고리즘 스터디에서는 동적 계획법 (Dynamic Programming) 에 대해 간단히 배우고, 이를 적용하여 문제를 풀어보는 시간을 가졌다.

동적 계획법이란 쉽게 말해 복잡한 문제들을 간단한 여러개의 문제로 나누어 하나씩 해결해나가는 것으로,

여러 알고리즘 문제 분류에서 쉽게 찾아 볼 수 있다. 이번에 풀어 본 문제도 간단한 동적 계획법에 해당한다.

계단 오르기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	25580	9813	7276	38.232%

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째, 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최대값을 구하는 프로그램을 작성하시오.

입력

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

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

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

예제 입력 1 

6
10
20
15
25
10
20

예제 출력 1 

75

출처

Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 초등부 4번

알고리즘 분류

• 다이나믹 프로그래밍

위 문제를 풀기 위해선 계단을 오르는 모든 경우의 수를 찾아 그 중 가장 큰 점수가 나오는 경우를 출력하면 된다.

제한만 없었다면.

위 문제의 조건에 따르면 최대 300개의 계단에 서로 다른 점수들이 들어가게 되는데 이 경우는 100% 시간초과를 받을 수 밖에 없기에 다른 방법을 이용해야 한다.

몇 번 삽질을 해본 결과 각 계단의 위치에서 두 가지 경우의 최대값을 가지는 것을 확인할 수 있었다.

1. 연속되는 계단의 수가 1개인 경우

2. 연속되는 계단의 수가 2개인 경우

1번 경우에는 이전 단계에서 한 번에 두 개의 계단을 오른 경우일 것이고, 2번 경우는 한 번에 하나의 계단을 오른 경우일 것이다.

따라서 이를 표로 나타내면

연속되는 계단 / 점수	10	20	15	25	10	20
1개	10	20	25	55	45	75
2개	(10)	30	35	50	65	65

위와 같이 정리된다.

따라서 이를 식으로 나타내면,

Maxscore[i][1] = score[i] + (Maxscore[i-2][1] 과 Maxscore[i-2][2] 중 큰 수)

Maxscore[i][2] = score[i-1] + score[i] + (Maxscore[i-3][1] 과 Maxscore[i-3][2] 중 큰 수)

...가 된다.

따라서 코드로 나타내면

#include <stdio.h>
 
int main(void) {
    int maxscore[302][3];
    int stair[302], cnt, bigscore;
    scanf("%d", &cnt);
    for (int i = 0; i <= cnt; i++) {
        scanf("%d", &stair[i]);
    }
 
    maxscore[0][1] = stair[0];
    maxscore[0][2] = stair[0];
    maxscore[1][1] = stair[1];
    maxscore[1][2] = stair[0] + stair[1];
    maxscore[2][1] = stair[2] + maxscore[0][2];
    maxscore[2][2] = stair[1] + stair[2];
 
    for (int i = 3; i < cnt; i++) {
        maxscore[i - 2][1] > maxscore[i - 2][2] ? bigscore = maxscore[i - 2][1] : bigscore = maxscore[i - 2][2];
        maxscore[i][1] = stair[i] + bigscore;
        maxscore[i - 3][1] > maxscore[i - 3][2] ? bigscore = maxscore[i - 3][1] : bigscore = maxscore[i - 3][2];
        maxscore[i][2] = stair[i] + stair[i - 1] + bigscore;
    }
 
    if (maxscore[cnt - 1][1] > maxscore[cnt - 1][2]) printf("%d", maxscore[cnt - 1][1]);
    else printf("%d", maxscore[cnt - 1][2]);
}

이렇게 된다.

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출한 시간
8866773	kyr9389	2579	맞았습니다!!	1116 KB	0 MS	C++ / 수정	885 B	22분 전
8866754	kyr9389	2579	틀렸습니다			C++ / 수정	895 B	24분 전
8866110	kyr9389	2579	틀렸습니다			C++ / 수정	1457 B	1시간 전
8866057	kyr9389	2579	틀렸습니다			C++ / 수정	1462 B	1시간 전
8864686	kyr9389	2579	틀렸습니다			C++ / 수정	1428 B	4시간 전
8864678	kyr9389	2579	출력 초과			C++ / 수정	1481 B	4시간 전

채점 준비중: 1개, 채점중: 1개, 채점 서버: 4개, 평균 채점 시간: 2.75초

삽질하느라 넘 힘들었다. 반례 찾기 왜 이리 힘든지...