[BOJ 2579] 계단 오르기 (Java, DP)
문제 링크
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
문제 풀이
- 시간복잡도 O(N)
처음 문제 풀이시 아래 (1)과 같이 점화식을 사용하여 문제 풀이를 수행했다
// i = 1, 2 일때 초기화 수행
DP[i] = DATA[i] + Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2])
이후에 더 나은 방식이 없는지 고민하던 중 예전에 구입했던 패스트 캠퍼스 강의를 확인했고,
2차원 배열을 사용하여 의미 부여를 통해 풀이하는 방식에 대해 이해 할 수 있었다.
| 1 | 2 | 3 | |
| DP[i][0] | 10 | 20 | Math.max(DP[1][0], DP[1][1]) + DATA[3] |
| DP[i][1] | 0 | 30 | DP[2][0] + DATA[3] |
- DP[i][0] := i -1 번째 계단을 밟지 않고, i 번째 계단에 도착하여 얻는 최대 점수
- DP[i][1] := i -1 번째 계단을 밟고, i 번째 계단에 도착하여 얻는 최대 점수 (DP[i - 1][0] + A[i])
- DP[i][0] 의 경우 두 계단을 뛰어 넘어서 현재 계단을 밟는 경우를 뜻함 (i - 2에서 찾아야 함)
- DP[i][1] 의 경우 이전 계단과 현재 계단을 밟는 경우를 뜻함 (이때 세 계단을 연속으로 밟는건 안된다고 명시되어 있기 때문에, DP[i - 1][0] 만이 대상이 된다)
https://fastcampus.co.kr/dev_online_codingtest
핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼
공유 설명 알고리즘부터 SQL까지 코딩테스트의 핵심 내용을 450문제에 모두 담은 강의로서, Quiz와 함께하는 4단계 학습 방식을 통해 스스로 문제를 푸는 문제 풀이 능력을 키울 수 있습니다. 가장
fastcampus.co.kr
ArrayIndexOfOutBound Exception의 경우 N = 1인 경우가 있는 것으로 생각됨
제출 코드
(1) 점화식 사용
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[] DP;
static int[] DATA;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
DATA = new int[N + 1];
for(int i = 1; i <= N; i++) {
DATA[i] = Integer.parseInt(br.readLine());
}
DP = new int[N + 1];
}
static void pro() {
DP[1] = DATA[1];
if(N >= 2) {
DP[2] = Math.max(DATA[1] + DATA[2], DATA[2]);
}
for(int i = 3; i <= N; i++) {
DP[i] = DATA[i] + Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2]);
}
System.out.println(DP[N]);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
(2) Bottom-Up 방식
2차원 배열 활용
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int[] A;
static int[][] DP;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
A = new int[N + 1];
for(int i = 1; i <= N; i++) {
A[i] = Integer.parseInt(br.readLine());
}
DP = new int[N + 1][2];
}
static void pro() {
DP[1][0] = A[1];
if(N >= 2) {
DP[2][0] = A[2];
DP[2][1] = A[1] + A[2];
}
for(int i = 3; i <= N; i++) {
DP[i][0] = Math.max(DP[i - 2][0], DP[i - 2][1]) + A[i];
DP[i][1] = DP[i - 1][0] + A[i];
}
System.out.println(Math.max(DP[N][0], DP[N][1]));
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
(3) Top-Down 방식
2차원 배열 활용
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int[] A;
static int[][] DP;
static void inputForTopDown() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
A = new int[N + 1];
for(int i = 1; i <= N; i++) {
A[i] = Integer.parseInt(br.readLine());
}
DP = new int[N + 1][2];
for(int i = 0; i <= N; i++) Arrays.fill(DP[i], -1); // -1 : 방문하지 않음 의미
DP[1][0] = A[1];
DP[1][1] = 0;
if(N >= 2) {
DP[2][0] = A[2];
DP[2][1] = A[1] + A[2];
}
int result = Math.max(executeByTopDown(N, 0), executeByTopDown(N, 1));
System.out.println(result);
}
static int executeByTopDown(int depth, int num) {
if(depth == 1 || depth == 2) return DP[depth][num];
if(DP[depth][num] != -1) return DP[depth][num];
int value = 0;
if(num == 0) {
value = Math.max(executeByTopDown(depth - 2, 0), executeByTopDown(depth - 2, 1)) + A[depth];
} else if(num == 1) {
value = executeByTopDown(depth - 1, 0) + A[depth];
}
return DP[depth][num] = value;
}
public static void main(String[] args) throws Exception {
inputForTopDown();
}
}