[백준] 2579번 '계단 오르기' - Java

https://www.acmicpc.net/problem/2579

---

문제

---

풀이

Bottom-UP: 작은 문제에서 큰 문제로

다이나믹 프로그래밍을 이용하여 풀이합니다.

 

dp배열은 해당 인덱스의 계단까지 올라갔을 경우의 점수의 합산을 값으로 넣습니다.

 

올라가는 경우는 O, 올라가지 않는 경우는 X라고 해봅시다.

i번째 계단에 올라간다고 할 경우, 

 

i-2, i-1, i 번째 계단은 X O O 혹은 O X O 가 될 수 있습니다.

 

만약 XOO의 경우에는 dp[i] = dp[i-3] + stair[i-1] + stair[i] 가 되고,

OXO의 경우에는 dp[i] = dp[i-2]+stai[i-3] 이 됩니다.

 

그래서 둘 중 큰 값을 dp[i]에 갱신시켜주면서 위로 올라가는 방식의 풀이입니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer n = Integer.valueOf(br.readLine());
		
		int[] stair = new int[n+1];
		for(int i=1; i<=n; i++) {
			stair[i] = Integer.valueOf(br.readLine());
		}
		
		int ans = solution(n, stair);
		System.out.println(ans);
	}
	
	public static int solution(int n, int[] stair) {
		int[] dp = new int[n+1];
		dp[0]=0;
		for(int i=1; i<=n; i++) {
			if(i == 1) dp[i] = stair[i];
			else if(i == 2) dp[i] = dp[i-1] + stair[i];
			else dp[i] = Math.max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i]);
		}
		
		return dp[n];
	}
}

---

Top-Down: 큰 문제에서 작은 문제로

Bottom-up의 문제와 같은 로직이지만, 재귀함수로 표현한 방식입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int n;
	static Integer[] dp;
	static int[] stair;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.valueOf(br.readLine());
		
		stair = new int[n+1];
		dp = new Integer[n+1];
		for(int i=1; i<=n; i++) {
			stair[i] = Integer.valueOf(br.readLine());
		}
		dp[0] = 0;
		int ans = recur(n);
		System.out.println(ans);
	}
	public static int recur(int i) {
		if(i == 1) return stair[1];
		else if(i==2) return recur(i-1)+stair[2];
		if(dp[i] == null) {
			dp[i] = Math.max(recur(i-3) + stair[i-1], recur(i-2)) + stair[i];			
		}
		return dp[i];
	}
}

 

---

회고

'포도주 시식' (https://www.acmicpc.net/problem/2156) 문제를 풀고 난 뒤에도 DP의 Top-Down, Bottom-Up이 이해가 되지 않아 풀이가 좋은 블로그를 발견하여 그 커리큘럼(?)을 따라봤습니다.

 

확실히 조금 낮춰서 풀어보니 이해가 완벽히 되는 것 같아요.