Java

[백준 2579] 계단 오르기 (JAVA)

iheeeee6-6 2023. 5. 23. 12:54
728x90

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

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

dp 문제로,

n번째 계단의 최대 값은 1) n -1번째 계단을 밟고 n-3번째 계단을 밟은 것 , 2) n-2번째 계단을 밟은 것 이다.

예를 들어 4번째 계단의 최대값은

1) 3번째 계단과 1번째 계단 값

           

       

    ㅁ 

2) 3번째 계단과 4번째 계단 값

            

        ㅁ

    ㅁ 

이다. 

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

public class Main {

	static int[] dp;
	static int[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int cnt = Integer.parseInt(br.readLine());

		arr = new int[cnt + 1];
		for (int i = 1; i <= cnt; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		dp = new int[cnt + 1];
		Arrays.fill(dp, -1);
		dp[0] = 0;
		dp[1] = arr[1];
		if (cnt >= 2) {
			dp[2] = arr[1] + arr[2];
		}

		find(cnt);
		System.out.println(dp[cnt]);
	}

	static int find(int n) {
		if (dp[n] == -1) {
			dp[n] = Math.max(find(n - 2), find(n - 3) + arr[n - 1]) + arr[n];
		}
		return dp[n];
	}
}

'Java' 카테고리의 다른 글

[백준 1937] 욕심쟁이 판다 (JAVA)  (0) 2023.05.23
[백준 2631] 줄세우기 (JAVA)  (0) 2023.05.23
[백준 1915] 가장 큰 정사각형 (JAVA)  (0) 2023.05.22
[백준 11501] 주식 (JAVA)  (0) 2023.05.21
[백준 1515] 수 이어 쓰기 (JAVA)  (0) 2023.05.17