백준 2096 풀이
https://www.acmicpc.net/problem/2096
내려가기
풀이
문제에서 주어지는 조건은 위의 그림과 같이 3개이다. 따라서 3개의 경우에 대해 각각 따로 구현하여 요구하는 값을 구해도 상관없지만 그렇게 푸는 것은 공부하는 의미가 없다고 생각한다.
위의 그림을 잘 보면 규칙을 발견할 수 있다.
현재 위치에 -1, 0, 1 을 더한 값으로 이동할 수 있다는 것이다.
이 규칙을 파악했다면 나머지는 dp로 풀 수 있다.
최대값 찾기만을 따로 보면
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j + d[k] >= 0 && j + d[k] < 3) {
dpMax[i][j + d[k]] = Math.max(dpMax[i][j + d[k]], dpMax[i - 1][j] + arr[i][j + d[k]]);
}
}
}
}
와 같이 구할 수 있다. dp 배열에 값이 쌓이고 최종적으로 마지막 행의 최대값을 구하면 그 값이 문제에서 요구하는 최대값과 같다.
최소값 구하는 것도 마찬가지로 구할 수 있다.
코드
import java.io.*;
import java.util.Arrays;
public class Main {
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
static int n, m;
static int[] d = {-1, 0, 1};
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first = br.readLine().split(" ");
n = Integer.parseInt(first[0]);
int[][] arr = new int[n][3];
int[][] dpMax = new int[n][3];
int[][] dpMin = new int[n][3];
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
for (int j = 0; j < 3; j++) {
arr[i][j] = Integer.parseInt(line[j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++)
dpMin[i][j] = Integer.MAX_VALUE;
}
for (int i = 0; i < 3; i++) {
dpMax[0][i] = arr[0][i];
dpMin[0][i] = arr[0][i];
}
//최대찾기
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j + d[k] >= 0 && j + d[k] < 3) {
dpMax[i][j + d[k]] = Math.max(dpMax[i][j + d[k]], dpMax[i - 1][j] + arr[i][j + d[k]]);
}
}
}
}
//최소 찾기
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (j + d[k] >= 0 && j + d[k] < 3) {
dpMin[i][j + d[k]] = Math.min(dpMin[i][j + d[k]], dpMin[i - 1][j] + arr[i][j + d[k]]);
}
}
}
}
int max = Arrays.stream(dpMax[n - 1]).max().getAsInt();
int min = Arrays.stream(dpMin[n - 1]).min().getAsInt();
bw.write(max + " " + min + "\n");
bw.close();
br.close();
}
}
Author And Source
이 문제에 관하여(백준 2096 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-2096-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)