2579번: 계단 오르기
https://www.acmicpc.net/problem/2579
# 코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] DP = new int[n + 1];
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// index = 0 은 시작점이다.
DP[1] = arr[1];
// N 이 1이 입력될 수도 있기 때문에 예외처리를 해줄 필요가 있다.
if (n >= 2) {
DP[2] = arr[1] + arr[2];
}
for (int i = 3; i <= n; i++) {
DP[i] = Math.max(DP[i - 2], DP[i - 3] + arr[i - 1]) + arr[i];
}
System.out.println(DP[n]);
}
}
- 현재 인덱스 i 에 대해 두 칸 전(i - 2)의 '메모이제이션 값'과 첫 칸 전(i - 1)의 값 + 셋 째칸 전(i - 3)의 '메모이제이션 값' 중 큰 값을 현재 i 계단의 값과 합하여 DP배열에 저장(Memoization)을 해주면 된다고 한다.
코드는 아래 블로그를 참고했다.
[백준] 2579번 : 계단 오르기 - JAVA [자바]
www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단
st-lab.tistory.com
'코딩테스트 > 자바 문제풀이' 카테고리의 다른 글
[CLASS 3: DP] 백준 9095 1, 2, 3 더하기 (0) | 2024.10.26 |
---|---|
[CLASS 3: BFS] 백준 2606 바이러스 (0) | 2024.10.25 |
[CLASS 3: DP] 백준 1463 1로 만들기 (0) | 2024.10.23 |
[CLASS 3: DP] 백준 1003 피보나치 함수 (0) | 2024.10.22 |
[CLASS 3: 구현] 백준 17219 비밀번호 찾기 (0) | 2024.10.21 |