728x90
https://www.acmicpc.net/problem/2579
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 |