DP - Dynamic Programming(동적 계획법)
🤷♂️ Dynamic Programming(동적 계획법)
- 기본적인 아이디어로 하나의
큰 문제를 여러 개의작은 문제로 나누어서 그 결과를 저장해 다시 큰 문제를 해결할 때 사용하는 방법 - 대표적으로
피보나치문제가 있다.
<JAVA 코드>
package BaekJoon.silver;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
1. 계단은 한번에 1 또는 2 계단 올라갈 수 있다.
2. 연속된 3개를 밟을 수 없다. 즉 1-2-3 은 불가
3. 마지막 계단은 반드시 밟아야한다.
- 최대값을 구하라
*/
public class Baek_9095 {
static int n;
static int climb(int[] stair) {
int[] answer = new int[n+1];
for(int i=0; i<n; i++) {
answer[i+1] = 0;
}
answer[0] = 0;
answer[1] = stair[1];
if(n == 1) {
return answer[n];
}
if(n >=2) {
answer[2] = stair[1] + stair[2];
for(int i=3; i<n+1; i++) {
answer[i] = Math.max(answer[i-3] + stair[i-1], answer[i-2] ) + stair[i];
}
}
return answer[n];
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bf.readLine());
int[] stair = new int[n+1];
for(int i=0; i<n; i++) {
stair[i+1] = Integer.parseInt(bf.readLine());
}
System.out.println(climb(stair));
}
}
- DP 로 문제를 풀어야하는 것 을 알아도 재귀를 생각해내는 것이 너무 쉽지않다.
DP 알고리즘
for(int i=3; i<n+1; i++) {
answer[i] = Math.max(answer[i-3] + stair[i-1], answer[i-2] ) + stair[i];
}연속해서 3개의 계단을 올라갈 수 없다. 따라서 만약 계단의 개수가 4개(n=4) 라고 한다면, 계단은 1층부터 n-3, n-2, n-1, n(4) 가 있을 것 이다.
계단을 올라가는 방법은 문제의 요구사항에 따라 다음과 같다.
1. n-3 을 밟고 n-1을 밟고 n으로 오는방법
2. n-2 를 밟고 n을 밟는 방법
1번의 경우를 생각해보자. 계단이 4층까지 있다고 하면 1->3->4층을 밟는다는 말이다. (1-2-3-4 , 2-3-4 는 불가)
2번의 경우를 생각해보자. 계단이 4층까지 있다고 하면 2->4층을 밟는다는 말이다. (2-3-4 는 불가)
즉, 각 계단마다 밟을 수 있는 최대값을 저장하는 배열을 answer로 둔다면,
answer[i] = Math.max(answer[i-3] + stair[i-1], answer[i-2] ) + stair[i] 이 성립한다.
나도 처음에 무지 이해가 안되었으니 좀 더 깊게 코드를 살펴보자.
이번엔 n=6(6층높이의 계단) 이 있다고 해보자.
answer[i-3] + stair[i-1] 은 무엇을 의미할까?
먼저 stair[i-1] 은 바로 직전 계단(5층)을 밟고 올라온단 말이다. 즉 6층계단일때 4층을 거치지 않고 5층을 밟고 올라온다. "4층을 거치지 않는다" 라는 말은 2계단전에서 5층으로 올라왔다는 말이되고, 즉 2계단전에서 올 수 있는 누적 최대합 answer[i-3] 에 5층을 밟은 수를 더해준 것 이다.
그렇다면 answer[i-2] 은 무엇을 의미할까? answer[i-2] 는 5층을 밟고 오지않고 4층에서 바로 6층으로 오게되는 경우의 수이다. 따라서 4층까지 오는 최대합인 answer[i-2] 을 구해와 Math.max(answer[i-3] + stair[i-1], answer[i-2]) 를 해주고 현재 계단인 6층의 수를 더해주면서 answer 배열을 업데이트한다.
아마 몇일 뒤에 문제를 풀면 또 까먹고 못풀지 않을까 싶다.
완벽히 이해하고 넘어가자
Backend Developer