[백준BOJ] 2096번 내려가기.java

 

백준 저지에서 내려가기를 자바를 통해 풀어 보았다. 

 

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

2096번: 내려가기

 

2096번 내려가기.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

2096번 내려가기 

문제

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.
먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

설명

dp를 사용해야 시간초과를 피할 수 있다. 백트래킹이나 dfs로도 풀 수 있을 듯 하지만 시간초과에 걸릴 것으로 예상하여 처음부터 dp를 통해 풀었다.

 

각 라인은 3개로 제한되어있다. 라인마다 세 개의 숫자는 각각 두번, 세번, 두번씩 확인해야한다. 따라서 한 라인당 7번 반복한다. 라인은 최대 100000이므로 dp를 활용하면 최대 700000번 계산되므로 시간 초과를 피할 수 있다.

 

dp를 저장할 공간을 만들고 최대, 최소에 따라 각 라인을 계산하여 값을 저장한다. 최종적으로 dp의 마지막 줄에는 각 번호가 가질 수 있는 최댓값 또는 최솟값이 저장되어 있다. 그 중에서도 최댓값 또는 최솟값을 반환한다.

 

최댓값을 뽑는 함수, 최솟값을 뽑는 함수를 따로 구현할 수도 있었지만 코드가 중복되는 부분이 많을 것 같아서 boolean 변수를 두어 하나의 함수로 사용가능하게 했다.

코드

//2096번 내려가기.java
package boj20211212;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 내려가기_2096 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		ArrayList<int[]> lines = new ArrayList<>();
		
		lines.add(new int[3]);
		for(int i=0;i<N;i++) {
			int[] line = new int[3];
			st = new StringTokenizer(br.readLine()," ");
			line[0] = Integer.parseInt(st.nextToken());
			line[1] = Integer.parseInt(st.nextToken());
			line[2] = Integer.parseInt(st.nextToken());
			lines.add(line);
		}
		
		sb.append(getPoint(N, lines, true)+" "+getPoint(N, lines, false));
		System.out.println(sb.toString());
	}
    
    static int getPoint(int N, ArrayList<int[]> lines, boolean maxOrmin) {
    	//maxOrmin이 true면 최댓값, false면 최솟값
    	int check =1;
    	if(!maxOrmin)check*=-1;
    	ArrayList<int[]> savePoint = new ArrayList<>();
    	
    	savePoint.add(new int[3]);
		for(int i=1;i<=N;i++) {
			int[] point = new int[3];
			if(!maxOrmin)Arrays.fill(point, 100*N);
			savePoint.add(point);
		}
			
		
		for(int i=1;i<=N;i++) {
			for(int j=0;j<3;j++) {
				int start = Integer.max(0, j-1);
				int end = Integer.min(j+1, 2);
				for(int l=start;l<=end;l++) {
					if(savePoint.get(i)[l]*check < (savePoint.get(i-1)[j]+lines.get(i)[l])*check) {
						savePoint.get(i)[l] = savePoint.get(i-1)[j]+lines.get(i)[l];
					}
				}
			}
		}
		
		int[] result = savePoint.get(N);
		Arrays.sort(result);
		int answer;
		if(maxOrmin)answer= result[2];
		else answer= result[0];
		return answer;
    }
}