백준온라인저지 2759 계단 오르기 자바풀이

본 문제는 동적계획법(DynamicPrograming)을 이용하여 풀어야 한다. 복잡한 문제를 간단한 여러개로 나누어서 해결하는 기법입니다. 그런 이유로 패턴(규칙)을 찾아 배열안에 초기값을 할당하고, for문을 돌리는 bottom-up 방식이나 재귀를 이용하는 top-down 방식이 있습니다. 

 

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

2579번: 계단 오르기

저는 bottom-up으로 데이터를 담을 용도로 배열을 선택했습니다. 사용자의 입력크기 만큼의 배열을 생성하고, 초기값을 넣었습니다.

 

이후에 고민을 했던게 for문을 통해 값을 더해나가야 하는데 그 부분을 어떻게 구상하냐는 것이였습니다. 가령, dp[4] 즉 계단 4까지의 최대값을 구한다면 계단 별로 1, 2, 4 혹은 1, 3, 4를 비교해야 할 것입니다. 일반적인 경우는 n>=3 이상일 때 이므로 for문의 초기값은 3이면 됐습니다. 

 

제가 이 부분을 제대로 하지 못했던 이유는 dp[] 라는 하나의 배열에 누적으로 더해나가려고 한 것에 있습니다. 이 계단 문제같은 경우는 연속 3개의 계단은 밟지 못한다 라는 조건이 있기 때문에 그런식으로 코딩을 하면 방법이 없었습니다. 

 

따라서 배열을 2개 구성해야 했습니다. 하나의 배열은 누적값, 하나의 배열은 계단의 점수가 있어야 합니다.

저세상 그림 ㅈㅅ

연속된 3계단을 밟지 못한다면 2가지의 경우를 고려할 수 있습니다. 2칸 올랐을 때, 목적지인 경우와 1칸 올랐을 때, 목적지인 경우입니다. 1번같은 경우는 바로 당연히 올라가기 전 계단에서 2칸 떨어진 계단의 누적점수+현재계단+목적지 점수를 합해야하고, 2번 같은 경우는 올라가기 전 계단의 누적합과 목적지의 점수를 합해야 합니다. 

 

계단 1과 계단 2는 배열의 값을 넣고, for문을 이용합니다.

package dynamicPrograming6;

import java.io.*;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int dp[];
	static int stairs[];
	static int n;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		
		stairs = new int[n+1];
		dp = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] = stairs[1];
		
		if(n>=2) { //초반 오류 방지
			dp[2] = stairs[1] + stairs[2]; // 계단 2의 누적합
		}
		for(int i=3; i<=n; i++) {
			dp[i] = Math.max(stairs[i] + dp[i-2], stairs[i-1]+ stairs[i] + dp[i-3]); //dp는 누적합, stairs는 계단의 점수
		}
		
		bw.write(String.valueOf(dp[n])+"\n");
		bw.flush();
		
		br.close();
		bw.close();
	}

}