[JAVA] BOJ(백준) - 정수 삼각형 - 1932

문제 내용

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

1932번: 정수 삼각형

---

문제 접근 방법

가장 처음 생각하려고 했던것은 더해가는 규칙을 찾는 것이었다.

이전에 RGB거리 문제를 풀었었고 최소비용을 구하기 위해 누적시켰던 것을 토대로 이문제 또한 합을 누적시켜 dp배열 값중 최댓값을 구하면 된다고 생각했다.

 

이때 주의할 점은 무조건 합치기만 하면안되고 왼쪽 대각선과 오른쪽 대각선의 값을 합쳤을때 최대로 되는 값만을 합쳐야 한다는 점이다.

 

그렇다면 값을 합치고 누적된 값을 저장해 놓는 방법을 알아보자.

 

1. for문

문제에서는 왼쪽 대각선과 오른쪽 대각선이라고 했지만 결국 우리는 저 삼각형을 입력받기 위해선 2차원 배열로 입력받아야 한다.

그리고 계산된 값을 저장해 놓기 위해 dp배열 또한 삼각형 배열과 같은 크기의 2차원 배열로 만들어야한다.

 

이때 삼각형 배열을 angle[][] 배열로 정의 하고, 현재 값의 인덱스가 i, j라고 한다면

left (왼쪽 값의 합) = dp[i][j] + angle[i+1][j];

right (오른쪽 값의 합) = dp[i][j] + angle[i+1][j+1];

이된다. 이때 주의 할점은 위에서 말했듯이 이미 계산된 값을 고려해서

dp[i+1][j] = Math.max(dp[i+1][j], left);

dp[i+1][j+1] = Math.max(dp[i+1][j+1], right);

을 해줘야한다.

 

위의 식을 이용해 문제 예시의 삼각형에 있는 7부터 시작하여 마지막값 까지 값을 누적시켜가며 dp 배열에 저장해 놓고 

마지막에 dp배열에서 최댓값을 구하면 된다.

참고로 dp[0][0]은 입력받은 angle[0][0]으로 초기화 시켜주고 시작한다.

 

 

2. 재귀

재귀를 이용하는 방법은 for문 방법과 비슷하지만 답을 구하는 방식이 다르다.

 

for문의 경우 dp[0][0]을 초기화 시켜서 (0, 0) 부터 (n-1, n-1) 까지 합을 누적시켜 가는 방식이지만,

재귀의 경우 dp[n-1][0] 부터 dp[n-1][n-1] 까지 초기화시켜서 dp[0][0] 쪽으로 합을 누적시켜가는 방식이다.

 

즉, 재귀의 경우 현재값은 다음값의 왼쪽 오른쪽 값중 최댓값과 합친 값을 다시 현재값에 할당해주는 방식이고 식으로 작성해 보면 dp[i][j] = Math.max(왼쪽 값, 오른쪽 값) + angle[i][j]; 가된다.

 

재귀는 위의 식을 이용해 풀어낼 수 있다.

 

말로 설명이 어려운데 코드를 보고 이해해 보자.

 

---

 

풀이

for문

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

public class BOJ_1932_1 {
	static int[][] angle; //입력받은 삼각형
	static int[][] dp; //dp배열
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		angle = new int[n][n];
		dp = new int[n][n]; //dp배열 크기도 삼각형 배열 크기와 같게 해준다.
		
		//angle배열 입력 및 dp배열 첫번째 값 초기화. 
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<=i; j++) {
				int temp = Integer.parseInt(st.nextToken());
				angle[i][j] = temp;
				if(i==0) {
					dp[0][0] = temp;
				}
			}
		}
		
		int left = 0; //왼쪽 대각선
		int right = 0; //오른쪽 대각선
		for(int i=0; i<n-1; i++) {//마지막 값은 빼줌. 다음값 더할게 없기 때문.
			for(int j=0; j<=i; j++) {
				left = dp[i][j] + angle[i+1][j];//전값에서 다음값 더함.
				right = dp[i][j] + angle[i+1][j+1];//전값에서 다음값 더함.
				dp[i+1][j] = Math.max(dp[i+1][j], left);//이미 계산된 값이 있다면 합의 최댓값을 넣어줌.
				dp[i+1][j+1] = Math.max(dp[i+1][j+1], right);//이미 계산된 값이 있다면 합의 최댓값을 넣어줌.
			}
			
		}
		
		int max = Integer.MIN_VALUE;
		for(int i=0; i<n; i++) {//최댓값 찾기.
			for(int j=0; j<n; j++) {
				max = Math.max(max, dp[i][j]);
			}
		}
		System.out.println(max);
	}
}

 

---

재귀

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

public class BOJ_1932_2 {
	static int[][] angle; //입력받은 삼각형
	static int[][] dp; //dp배열
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int n = Integer.parseInt(br.readLine());
		angle = new int[n][n];
		dp = new int[n][n]; //dp배열 크기도 삼각형 배열 크기와 같게 해준다.
		
		//angle배열 입력 및 dp배열 마지막 행값 초기화. 
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<=i; j++) {
				int temp = Integer.parseInt(st.nextToken());
				angle[i][j] = temp;
				if(i==n-1) {
					dp[i][j] = temp;
				}
			}
		}
		int max = maxValue(0, 0, n);
		System.out.println(max);
	}
	
	public static int maxValue(int i, int j, int n) {
		if(i==n-1) {//마지막 행일때 초기화 해놓은거 반환
			return dp[i][j];
		}
		if(dp[i][j]==0) {//저장안된 부분일때
			//계산된 현재(dp[i][j])의 값은 다음 값의 왼쪽과 오른쪽중 더큰 값과 현재(angle[i][j])값 더함. 
			dp[i][j] = Math.max(maxValue(i+1,j,n), maxValue(i+1, j+1,n)) + angle[i][j];
		}
		return dp[i][j];
	}
}

---

마치며

문제를 말로 설명하기 참 어려운것같다...그래도 나는 최선을 다해서 풀어쓴 것이기 때문에 코드를 보면 이해할 수 있다고 생각한다.