문제
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.
예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째, 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.
계단 오르는 데는 다음과 같은 규칙이 있다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최대값을 구하는 프로그램을 작성하시오.
출력
첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최대값을 출력한다.
알고리즘 분류
조건
1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다.
2. 연속된 3칸은 오를 수 없다.
3. 마지막 계단은 무조건 밟아야한다.
풀이
마지막 계단을 무조건 밟아야한다면 두가지로 분류할 수 있다.
1. 전칸을 밟고 마지막칸을 밟는 경우
--> 마지막 칸이 n이라면 n-1 + n이 된다.
2. 전전칸을 밟고 마지막칸을 밟는 경우
--> 마지막 칸이 n이라면 n-2 + n이 된다.
하지만 1번의 경우 연속으로 3칸을 밟을 수 없으므로 전칸을 밟고 현재칸을 밟는경우에는 조건을 추가해주어야한다.
1. 전칸을 밟는 경우에는 n-2번째 칸을 밟을 수 없다. (즉, 전전전칸 + 전칸 + 현재칸이 되어야한다.)
--> n-3 + n-1 + n으로 쓸 수 있다.
위와 같이 계산하면 3칸이 연속되는 경우는 제외하고 계산할 수 있다.
구현
입력을 받는 배열과 각 계산을 저장하는 배열 2개를 생성한다.
(입력을 받는 배열을 사용하여 계산하게 되면 원래 계단의 점수가 사라질 수 있다.)
점화식 구현
dp배열에는 i번째 계단까지의 최대값을 저장해놓는 배열이고, stair배열은 문제에서 주어지는 점수를 저장한 배열이다.
전전칸을 밟고 현재칸을 밟는경우 -> 전전칸까지의 최대값 + 현재칸
전전전칸을 밟고 전칸을 밟고 현재칸을 밟는 경우 -> 전전전칸까지의 최대값 + 전칸 + 현재칸
|
|
dp[i-2]+stair[i]
stair[i-1]+stair[i]+dp[i-3] |
cs
|
현재 칸까지의 최대값을 구하기 위해서는 조건 두개 중 최대값을 dp배열에 저장해두면 된다.
|
|
int Max(int a, int b) {
return a > b ? a : b;
}
dp[i] = Max(dp[i-2]+stair[i], stair[i-1]+stair[i]+dp[i-3]); |
cs |
i=0 ~ n-1 까지 돌리면 dp배열의 n-1번째 배열에는 최대값이 저장되는것을 알 수 있다.
하지만 for문을 통해 i=0부터 돌리게되면 dp[i-3] 에서 i값이 음수값으로 나오는 것을 알 수 있다. 그럼 i = 3부터 돌려야 하는것을 알 수 있다. 그럼 dp[0] ~ dp[2] 까지의 초기값을 조건에 맞게 넣어주어야 한다.
dp[0] 일 경우는 1칸을 갔을 경우이다.
--> 1칸을 가기위해서는 단 하나의 경우 밖에없다.
dp[1] 일 경우는 2칸을 갔을 경우이다.
--> 2칸을 가기위해서는 1칸+1칸 갔을 경우와 한번에 2칸을 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.
dp[2] 일 경우는 3칸을 갔을 경우이다.
--> 3칸을 가기위해서는 1칸+2칸 갔을 경우와 2칸+1칸 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.
|
|
dp[0] = stair[0];
dp[1] = Max(stair[0]+stair[1],stair[1]);
dp[2] = Max(stair[0]+stair[2],stair[1]+stair[2]); |
cs |
전체 소스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
#include <iostream>
using namespace std;
int n,stair[301];
int dp[301];
int Max(int a, int b) {
return a > b ? a : b;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> stair[i];
}
dp[0] = stair[0];
dp[1] = Max(stair[0]+stair[1],stair[1]);
dp[2] = Max(stair[0]+stair[2],stair[1]+stair[2]);
for (int i = 3; i < n; i++) {
dp[i] = Max(dp[i-2]+stair[i], stair[i-1]+stair[i]+dp[i-3]);
}
cout << dp[n - 1] << '\n';
return 0;
}
|
cs |
출처: http://kwanghyuk.tistory.com/4
JAVA 코드:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] stair = new int[n];
int[] dp = new int[n];
for(int i = 0; i < n; i++){
stair[i] = sc.nextInt();
}
sc.close();
dp[0] = stair[0];
dp[1] = max(stair[1], stair[0] + stair[1]);
dp[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
for(int i = 3; i < n; i++){
dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
}
System.out.println(dp[n - 1]);
}
public static int max(int a, int b){
return a > b ? a : b ;
}
}
DP란
동적 계획법의 원리는 매우 간단하다. 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다. 이에 우리는 동적 계획법을 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이라고 생각할 수 있다. 그러나 문제가 가능한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우, 동적 계획법은 최적의 해법이라고 말할 수 있다.
때로는 단순한 재귀함수에 저장 수열(이전의 데이터를 모두 입력하는 수열)을 대입하는 것 만으로도 최적해를 구할 수 있는 동적 알고리즘을 찾을 수 있다. 그러나 대다수의 문제는 이보다 훨씬 더 복잡한 프로그래밍을 요구한다. 그 중에 일부는 여러 개의 매개 변수를 이용하여 재귀 함수를 작성해야 하는 것도 있고, 아예 이러한 방법으로 동적 알고리즘을 짤 수 없는 문제 또한 존재한다. 이러한 퍼즐로는 대표적으로 Egg Dropping Puzzle이 있다.
동적 계획법은 위에서 설명했듯이, 주먹구구식의 방법이라는 단점이 있다. 이러한 단점을 극복하기 위하여, 동적 계획법 대신 그리디 알고리즘 이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 MST(최소 비용 나무 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증되었다.
그리디 알고리즘과 동적 계획법을 비교하자. 우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 반면 그리디 알고리즘은 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다.
물론 동적 계획법으로 경로를 검색하는 동안 우리가 운전을 잠깐 쉬어야 하듯이, 우리는 동적 계획법을 사용하면 약간의 시간이 걸린다는 단점이 있다. 그러나 이렇게 얻어낸 경로는 (교통 환경이 변하지 않았다는 가정 하에) 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다. 반면 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다. 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 즉, 동적 계획법은 그리디 알고리즘에 비해 시간적으로는 효율적이지 못할 수는 있어도, 그 결과에 대해서는 효율적인 값을 구할 수가 있다.
[출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95]
