[Java] 백준 2096번 내려가기 문제 952hi의 접근방법

https://www.acmicpc.net/problem/2096

2096번: 내려가기

---

1. 접근방법

문제를 읽자마자 백준에서 RGB거리라는 문제가 생각이 났다.  크게 다를게 없어서 바로 dp 다이나믹 프로그래밍 알고리즘을 사용해서 문제를 풀었다.

 

간단하게 1번열은 직전 1,2 열 2번열은 직전 1,2,3열 3번열은 직전 2,3열의 영향이 다음으로 합쳐지는 방식이기 때문에 dp를 사용했고 3차원배열을 사용해 최소 최대를 구해줬다.

2. 느낀점

다 풀고 3차원배열안쓰면 더 빠를거 같은 느낌이 들긴했는데 크게 차이는 없을 것 같았다.

min max안쓰고 조건문쓰면 빠른데 이 부분도 크게 생각하지 않았다.

 

신경쓴 부분은 반복분 2번 사용안하고 입력받으면서 바로 계산해서 다음번에 추가하는 방식을 사용해봤는데 오히려 시간이 추가됐다..? 

 

이부분은 의외였다.

3. 코드

import java.io.*;
public class boj2096 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() {
			if (bufferPos == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferPos = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
		}

		int nextInt() {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
	public static void main(String[] args) {
		Reader in = new Reader();
		int n = in.nextInt();
		int[][][] comp = new int[n][3][2]; // 0 최대 1 최소
		int check;
		
		for(int i=0;i<n;i++) {
			comp[i][0][0] = in.nextInt();
			comp[i][0][1] = comp[i][0][0];
			
			comp[i][1][0] = in.nextInt(); 
			comp[i][1][1] = comp[i][1][0];
			
			comp[i][2][0] = in.nextInt();
			comp[i][2][1] = comp[i][2][0];
		}
		
		for(int i=1;i<n;i++) {
			comp[i][0][0] = Math.max(comp[i-1][0][0]+comp[i][0][0], comp[i-1][1][0]+comp[i][0][0]);
			comp[i][0][1] = Math.min(comp[i-1][0][1]+comp[i][0][1], comp[i-1][1][1]+comp[i][0][1]);
			
			check =Math.max(comp[i-1][0][0]+comp[i][1][0], comp[i-1][1][0]+comp[i][1][0]);
			comp[i][1][0] = Math.max(check, comp[i-1][2][0]+comp[i][1][0]);
			check =Math.min(comp[i-1][0][1]+comp[i][1][1], comp[i-1][1][1]+comp[i][1][1]);
			comp[i][1][1] = Math.min(check, comp[i-1][2][1]+comp[i][1][1]);
			
			comp[i][2][0] = Math.max(comp[i-1][1][0]+comp[i][2][0], comp[i-1][2][0]+comp[i][2][0]);
			comp[i][2][1] = Math.min(comp[i-1][1][1]+comp[i][2][1], comp[i-1][2][1]+comp[i][2][1]);
		}
		int min=comp[n-1][0][1],max=comp[n-1][0][0];
		for(int i=1;i<3;i++) {
			if(comp[n-1][i][1]<min) min =comp[n-1][i][1];
			if(comp[n-1][i][0]>max) max =comp[n-1][i][0];
		}
		System.out.println(max+" "+min);
	}
}

 

 

그래도 1페이지 장식했다.