안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅은 백준 DP 문제 내려가기 자바 풀이를 진행하도록 하겠습니다.
문제 출처: https://www.acmicpc.net/problem/2096
2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
1. 풀이 소스
import java.io.*;
import java.util.StringTokenizer;
import static java.lang.Integer.parseInt;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = parseInt(br.readLine());
int[][] map = new int[n][3];
int[][][] dp = new int[n][3][2]; // 최대, 최소 저장
for (int row = 0; row < n; row++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int col = 0; col < 3; col++) {
map[row][col] = parseInt(st.nextToken());
}
}
dp[0][0][0] = dp[0][0][1] = map[0][0]; // 초기화는 map에 있는 값으로 설정
dp[0][1][0] = dp[0][1][1] = map[0][1];
dp[0][2][0] = dp[0][2][1] = map[0][2];
for (int row = 1; row < n; row++) { // 왼쪽은 왼, 중앙 / 중앙은 왼, 중, 오 / 오른쪽은 중, 오 순서로 dp 진행
// 최대
dp[row][0][0] = Math.max(dp[row - 1][0][0], dp[row - 1][1][0]) + map[row][0];
dp[row][1][0] = Math.max(Math.max(dp[row - 1][0][0], dp[row - 1][1][0]), dp[row - 1][2][0]) + map[row][1];
dp[row][2][0] = Math.max(dp[row - 1][1][0], dp[row - 1][2][0]) + map[row][2];
// 최소
dp[row][0][1] = Math.min(dp[row - 1][0][1], dp[row - 1][1][1]) + map[row][0];
dp[row][1][1] = Math.min(Math.min(dp[row - 1][0][1], dp[row - 1][1][1]), dp[row - 1][2][1]) + map[row][1];
dp[row][2][1] = Math.min(dp[row - 1][1][1], dp[row - 1][2][1]) + map[row][2];
}
int max = Math.max(Math.max(dp[n - 1][0][0], dp[n - 1][1][0]), dp[n - 1][2][0]);
int min = Math.min(Math.min(dp[n - 1][0][1], dp[n - 1][1][1]), dp[n - 1][2][1]);
System.out.println(max + " " + min);
}
}
2. 풀이 중점 사항
문제에서 요구하는 것은 최대, 최소를 출력하여야 하므로 dp를 3차원 배열로 선언하여 각각 최대, 최소를 매 상황에 맞게 구하는 것이 중요한 포인트였습니다.!
N이 최대 10만이고, 최대 숫자는 9 이므로 max의 범위는 90만이므로 int 3차원 배열로 설정하였습니다.
이상으로 백준 DP 문제 내려가기 풀이를 마치도록 하겠습니다. 감사합니다.!
'Algorithm' 카테고리의 다른 글
| [Algorithm] 백준 DP 문제 - 외판원 순회(2098) 자바 풀이 (1) | 2023.05.18 |
|---|---|
| [Algorithm] 백준 DP 문제 - 줄세우기(2631) 자바 풀이 (0) | 2023.05.18 |
| [Algorithm] 백준 DP 문제 - 암호코드(2011) 자바 풀이 (0) | 2023.05.17 |
| [Algorithm] 백준 문자열 문제 - 동물원(1309) 자바 풀이 (0) | 2023.05.17 |
| [Algorithm] 백준 문자열 문제 - Java vs C++(3613) 자바 풀이 (2) | 2023.05.17 |