BOJ2579_계단 오르기

개요

제한된 조건의 연속합을 구현해봅시다

문제 접근

문제에서 제시하는 제한 조건으로
1. 계단은 한 계단씩 또는 두 계단식 오를 수 있음.
2. 연속된 세 개의 계단을 모두 밟아서는 안됨.
3. 마지막 도착은 반드시 밟아야함.

계단의 계수 : 0 < N < 301
점수 : 0 < score < 10,000

점수를 받을 수 있는 최댓값은
대충 300 X 10,000 = 3,000,000

타입은 무난하게 int형 타입으로 해도 상관 없을거 같다

제한 시간은 1초로 일단 중첩 반복문의 사용을 자제하는 쪽으로 생각해보자 (상관은 없을거 같지만)

재귀호출하여 문제를 풀어 볼려고 접근했지만 이문제의 2번째 제한 조건 때문에 상당히 까다롭게 느껴져 bottom-up방식 반복문으로 접근을 해보았다

우선 N번째 계단에 대한 점화식부터 설계를 해보자
그렇다면 과연 N번째 계단의 최댓값은 어떻게 구할것인가?

(아 귀찮아 그림판 🙃)

N번째 계단으로 올수 있는 경우는 위 그림과 같이 표현 해볼 수 있을거 같다

첫번째 : N-3번째 계단을 밟고 N-1번째 계단을 밟아 오는 것
두번째 : N-2번째 계단을 밟아 오는 것

그외, 연속해서 세번씩 밟은 경우는 제한되므로 제외한다.

케이스별 시작점: dp[n-3] / dp[n-2]

case 1 : dp[n-3]은 N-1칸을 밟고 오기 때문에 N-1계단의 점수를 합산하여(dp[n-3] + arr[n-1])

case 2 : dp[n-2]은 그냥 오기 때문에 (dp[n-2])

따라서 N번째 계단에 올 수 있는 두가지 경우 중 가장 큰 값에 N번째 계단의 점수를 더하면 N번째 칸의 올 수 있는 가장 큰 값이 되시겠다

이를 점화식으로 표현하면

$dp[n] = Math.max(dp[n-2], dp[n-3] + arr[n-1])+arr[n]$으로 표현할 수 있을거 같다

이를 구현한 코드이다

코드

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

public class Main {
		

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n + 1];
		int[] dp = new int[n + 1];
		
		
		for(int i = 1; i <= n; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
        // dp[1] 과 dp[2]의 초기화 식
		for(int i = 1; i <= 2; i++) { 	
			// n이 1일 경우
            if(i > n)
				break;
			dp[i] = arr[i] + dp[i - 1];
		}
		
		for(int i = 3; i <= n; i++)
			dp[i] = Math.max(dp[i-2],dp[i-3] + arr[i-1]) + arr[i];
		
		bw.write(String.format("%d", dp[n]));
		bw.close();
	}
}

필자는 배열의 크기를 N의 최댓값으로 초기화하지 않았기 때문에 dp[1] 과 dp[2]의 초기화식을 위 코드와 같이 구성해보았다