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

 

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

2096번: 내려가기

 

최근에 함수형 인터페이스를 공부했었는데 활용하기 좋은 문제 인거 같아 정리해보고자 한다.

 

문제 분석

 

3칸씩 n개의 줄로 주어지는 숫자들에서 숫자를 하나씩 골라 더했을 때 최대값, 최소값을 구하면 된다.

이때 숫자를 고르는 조건은 현재 숫자를 고른 행,열을 기준으로 다음 행에서는 현재열과 인접한 열의 숫자만

고르는게 가능하다.

 

즉 현재 고른숫자가 제일 왼쪽이라면 다음에 고를수 있는 숫자는 왼쪽과 가운데,

제일 오른쪽이라면 오른쪽과 가운데,

가운데라면 세칸 모두를 고를수 있게 되는것이다.

 

문제의 이해 자체는 상단의 링크에서 그림으로 잘 설명되어 있으니 쉽게 할수 있을것이다.

 

 

풀이

 

전형적인 DP문제라고 볼수 있겠다.

이때 문제를 풀기 위한 아이디어는 현재행을 기준으로 다음행을 고른다란 생각보단

현재형을 기준으로 이전의 최소가 되는 행을 선택해 저장한다라고 생각하면 될것이다.

 

즉 현재행의 세숫자를 모두 고른다 가정하고 고를때의 최소값이 되는 조건을 생각해보면

왼쪽의 숫자를 고르게 된다면 이전행에서는 제일 왼쪽이나 가운데 행에서만 골랐을 경우 이므로

이전행의 왼쪽과 가운데중 최소값이 되는 경우와 현재 행의 왼쪽의 숫자를 더해 저장하면 될것이다.

 

 

 

 

오른쪽의 숫자를 고르는 경우와 가운데 숫자를 고르는 경우모두 같은 방법으로 진행될것이다.

이를 그림으로 표현하면 다음과 같다.

 

 

 

 

이 과정을 모든 행에서 반복을 통해 연산 값을 저장하길 반복해 나가면 최소값, 최대값을 구할수 있다.

 

그렇다면 함수형 인터페이스는 어디에 활용하기 좋은가?

위의 로직을 메소드로 구현한다면 값비교, 연산, 저장 (반복)의 형태일것이고 최대값, 최소값을 구할때

모두 같은 구조를 갖는것을 알 수 있다.

 

같은 구조를 갖되 내부에서 비교하는 부분만 다르게 한다면

같은 메소드로 원하는 두가지 값 모두를 구할수 있다.

 

 

구현

 

 

값을 비교해 작은 값을 리턴하거나 큰값을 리턴하는 함수는 Math.max, Math.min을 사용할것이다.

두 함수 모두 두개의 정수 파라미터를 갖고 하나의 정수값을 리턴한단 공통점을 갖는다.

그럼 이런 형태를 사용하기 좋은 함수형 인터페이스를 찾아보도록 하겠다.

 

 

https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html

java.util.function (Java Platform SE 8 )

 

공식문서를 뒤적거리면,

 

https://docs.oracle.com/javase/8/docs/api/java/util/function/IntBinaryOperator.html

IntBinaryOperator (Java Platform SE 8 )

 

IntBinaryOperator란 녀석을 사용하면 될듯하다.

 

그럼 바로 코드로 적용해보도록 하겠다.

 

먼저 각 행렬의 값을 모두 저장할 배열, 계산한 값을 저장할 배열 이렇게 두개 배열을 선언해 사용하겠다.

 

	private int[][] dp; // 계산해 저장할 배열
	private int[][] metrix; // 행렬의 기본값

 

 

이때 계산해 저장할 배열에서 첫번째 행은 이전에서 고를수가 없으므로

초기값을 기본값과 동일하게 넣어주도록 하겠다.

 

 

		for(int i = 0; i < 3; i++) {
			dp[0][i] = metrix[0][i];
		}

 

 

그리고 이전행의 왼쪽과 가운데의 비교값, 가운데와 오른쪽의 비교값을

현재행과 더해 저장하길 반복하기만 하면 된다.

 

	private int calculate(IntBinaryOperator oper) {
		int l = 0;
		int r = 0;
		
		for(int i = 1; i <= n; i++) {
			l = oper.applyAsInt(dp[i - 1][0], dp[i - 1][1]);
			r = oper.applyAsInt(dp[i - 1][1], dp[i - 1][2]);
			
			dp[i][0] = l + metrix[i][0];
			dp[i][1] = oper.applyAsInt(r, l) + metrix[i][1];
			dp[i][2] = r + metrix[i][2];
		}
		
		return oper.applyAsInt(
				oper.applyAsInt(dp[n][0], dp[n][1]), dp[n][2]);
	}

 

 

 

이제 예제를 출력해보면 답을 맞게 내고 있음을 확인 할 수 있다.

 

 

 

아래는 코드의 전문이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.IntBinaryOperator;

public class Boj2096 {

	public static void main(String[] args) {
		BOJ2096Sol instance = new BOJ2096Sol();
		instance.run();
	}

}

class BOJ2096Sol {
	
	private int[][] dp;
	private int[][] metrix;
	private int n;
	
	private void init() throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(in.readLine());
		dp = new int[n + 1][3];
		metrix = new int[n + 1][3];
		for(int i = 0; i < n; i++) {
			init(in.readLine(), i);
		}
		for(int i = 0; i < 3; i++) {
			dp[0][i] = metrix[0][i];
		}
	}
	
	private void init(String input, int i) {
		StringTokenizer st = new StringTokenizer(input, " ");
		for(int j = 0; j < 3; j++) {
			metrix[i][j] = Integer.parseInt(st.nextToken());
		}
	}
	
	private int calculate(IntBinaryOperator oper) {
		int l = 0;
		int r = 0;
		
		for(int i = 1; i <= n; i++) {
			l = oper.applyAsInt(dp[i - 1][0], dp[i - 1][1]);
			r = oper.applyAsInt(dp[i - 1][1], dp[i - 1][2]);
			
			dp[i][0] = l + metrix[i][0];
			dp[i][1] = oper.applyAsInt(r, l) + metrix[i][1];
			dp[i][2] = r + metrix[i][2];
		}
		
		return oper.applyAsInt(
				oper.applyAsInt(dp[n][0], dp[n][1]), dp[n][2]);
	}
	
	private void printAns() {
		System.out.print(
				calculate(Math::max) + " " + calculate(Math::min));
	}
	
	void run() {
		try {
			init();
			printAns();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}