[백준] 2096 - 내려가기 (JAVA)

1. 소요시간 : 11분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 다이나믹 프로그래밍, 슬라이딩 윈도우
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2096
8. 푼 날짜 : 2023.03.20

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

정수 삼각형이나 RGB 거리 문제와 굉장히 흡사했다.
그 이전까지의 최대값을 기억하고 있다가 새로 만나는 값에 더해주면 된다.

3. 풀이과정

1. arr[i][0] , arr[i][1], arr[i][2] 에 각각 값을 담는다.
2. 점화식을 유도한다.
   여기서의 점화식은
   dp[i][n] = max(dp[i-1][n-1],dp[i-1][n],dp[i-1][n+1]) + arr[i][n] 이다. 하지만 n 이 3까지 이고,
   n이 1일때는 n-1 이 1,2
   n이 2일때는 n-1 이 1,2,3
   n이 3일때는 n-1 이 2,3 일떄만 구해주면 된다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;


		int n=Integer.parseInt(br.readLine());
		
		
		int arr[][]=new int[n+1][3];
		int maxDP[][]=new int[n+1][3];
		int minDP[][]=new int[n+1][3];
		for(int i=1;i<arr.length;i++) {
			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());
		}
		
		for(int i=1;i<maxDP.length;i++) {
			maxDP[i][0]=Math.max(maxDP[i-1][0],maxDP[i-1][1])+arr[i][0];
			maxDP[i][1]=Math.max(maxDP[i-1][0],Math.max(maxDP[i-1][1],maxDP[i-1][2]))+arr[i][1];
			maxDP[i][2]=Math.max(maxDP[i-1][1],maxDP[i-1][2])+arr[i][2];
			
			minDP[i][0]=Math.min(minDP[i-1][0],minDP[i-1][1])+arr[i][0];
			minDP[i][1]=Math.min(minDP[i-1][0],Math.min(minDP[i-1][1],minDP[i-1][2]))+arr[i][1];
			minDP[i][2]=Math.min(minDP[i-1][1],minDP[i-1][2])+arr[i][2];
		}
		int max=Math.max(maxDP[n][0],Math.max(maxDP[n][1],maxDP[n][2]));
		int min=Math.min(minDP[n][0],Math.min(minDP[n][1],minDP[n][2]));
		System.out.println(max+" "+min);

	}
}

5. 결과

java 15로 제출하면 메모리 초과가 떴다.
기본 메모리 제한이 4MB이고
java 8과 java 11은 256MB 이기 때문에 java 8 로 수정해서 제출하니 정답이 나왔다.

6. 회고

문제를 풀고 다른 사람의 풀이를 봤는데
나는 dp[n+1][3] , arr[n+1][3] 으로 크기를 지정해 준 것을
dp[3] 으로 지정하고 arr은 아예 만들지 않을 수도 있었다. 그 사람의 코드를 보고 좀 쇼킹받았다.
내가 제출한 코드중 2번째 제출한 것이 다른 블로그의 코드를 제출한 것인데 메모리가 사용량이 크게 줄어들었다.

다음번에 풀 때는 그 풀이법을 참고해서 메모리 사용량을 나도 줄여보도록 해야겠다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212