[Baekjoon/백준] 2579번: 계단 오르기(C/C++)
단계별로 풀어보기 15단계(동적 계획법 1) 7번 문제
https://www.acmicpc.net/step/16
동적 계획법 1 단계
i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다.
www.acmicpc.net
백준 2579번: 계단 오르기
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
문제 설명
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
입력과 출력
입력: 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.
출력: 첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.
접근 방법
이번 문제는 계단 개수를 입력하고 각 계단의 점수를 입력해서, 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제다. 계단 오르기 게임은 한번에 한계단 또는 두 계단씩 오를 수 있으며, 시작 지점을 제외한 3개 계단을 연속해서 밟을 수는 없고, 마지막 계단은 무조건 밟아야 하는 규칙이 있다.
마지막 계단은 무조건 밟아야한다는 조건과 3개 계단을 연속해서 밟을수 없다는 조건을 생각하면, 마지막 계단을 N이라고 했을때 N을 밟기 위해서는 N - 1을 밟았을때는 N-2를, N - 2를 밟았을때는 N - 1을 밟으면 안된다는 조건을 만들 수 있다. 이를 활용해서 N번째를 밟을때의 최댓값을 구하기 위해서는 N - 2번째까지의 최댓값과 N - 3번까지의 최댓값과 N - 1번 값을 더한 값 중 더 큰 값과 N번째 계단 값을 더하면 된다.
코드
#include <stdio.h>
#define MAX 301
int findMAX(int x, int y) {
return x > y ? x : y;
}
int main(int argc, char *argv[]) {
int N, stair[MAX];
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%d", &stair[i]);
int max[MAX] = { 0, stair[1], stair[1] + stair[2] };
for (int i = 3; i <= N; i++)
max[i] = stair[i] + findMAX(max[i - 2], stair[i - 1] + max[i - 3]);
printf("%d\n", max[N]);
return 0;
}결과
