백준 2096번 - 내려가기
문제 풀이
탑 다운 dp 연습 겸 탑 다운 방식으로 풀이했다.
최대 값, 최소 값을 모두 구해야 하므로 두 개의 dp배열, 최대 값을 구하는 함수, 최소 값을 구하는 함수 두가지를 작성했다.
d배열은 최대 값을 저장하는 배열, d2배열은 최소 값을 저장할 배열이다.
최대 최소를 저장해야하므로 각각 -1, 987654321로 초기화 시켜주었다.
기저 사례로 i == n-1일 경우 arr[i][j]를 반환해 준다.
그 외에는 현재의 최대 또는 최소값 = 현재 위치한 배열의 값 + 그 다음 줄에서 얻을 점수의 최대 값 또는 최소 값이라고 생각하면
d[0][0], d[0][1], d[0][2] 중에서 최대값을 얻어낼 수 있고
d2[0][0], d2[0][1], d[0][2] 중에서 최소 값을 얻어낼 수 있다.
문제 링크
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] d;
static int[][] d2;
static int[][] arr;
static int solve(int i, int j) {
if (d[i][j] != -1)
return d[i][j];
if (i == n - 1)
return arr[i][j];
d[i][j] = 0;
if (j == 0)
d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), solve(i + 1, 1));
else if (j == 1)
d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), Math.max(solve(i + 1, 1), solve(i + 1, 2)));
else if (j == 2)
d[i][j] = arr[i][j] + Math.max(solve(i + 1, 1), solve(i + 1, 2));
return d[i][j];
}
static int solve2(int i, int j) {
if (d2[i][j] != 987654321)
return d2[i][j];
if (i == n - 1)
return arr[i][j];
d2[i][j] = 0;
if (j == 0)
d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), solve2(i + 1, 1));
else if (j == 1)
d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), Math.min(solve2(i + 1, 1), solve2(i + 1, 2)));
else if (j == 2)
d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 1), solve2(i + 1, 2));
return d2[i][j];
}
static int n;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
d = new int[n][3];
d2 = new int[n][3];
arr = new int[n][3];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
Arrays.fill(d[i], -1);
Arrays.fill(d2[i], 987654321);
}
int max = Math.max(Math.max(solve(0, 0), solve(0, 1)), solve(0, 2));
int min = Math.min(Math.min(solve2(0, 0), solve2(0, 1)), solve2(0, 2));
System.out.println(max + " " + min);
}
}
Author And Source
이 문제에 관하여(백준 2096번 - 내려가기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pjh612/백준-2096번-내려가기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)