[Java] 백준 1932.정수 삼각형

➡️문제 링크

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

 

 

💡아이디어

DP

 

 

✏️문제 풀이

1. DP - 성공

대각선 왼쪽은  (j-1), 대각선 오른쪽은 j로 설정해서

현재 최댓값은 이전 라인의 대각선 왼쪽과 대각선 오른쪽 값 중 최댓값을 선택해 갱신하도록 했다

처음에는 result값에 가장 꼭대기에 있는 값을 초기값으로 설정해야하나 고민하다

본문에 있는 예제 테스트는 다 결과값이 나오길래 안 넣었는데

 N = 1인 경우에는 틀려서 map[0][0]을 초기값으로 설정했다

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] map = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < i+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int result = map[0][0];
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < i+1; j++) {
				int left = 0;
				int right = 0;
				if(j-1 >= 0) left = map[i-1][j-1];
				if(j <= i) right = map[i-1][j];
				map[i][j] += Math.max(left, right);
				
				result = Math.max(result, map[i][j]);
			}
		}
		
		// 정답
		System.out.println(result);
	}

}

 

 

근데 left, right 부분이 지저분한 것 같아서 아래처럼 개선해봤다

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] map = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < i+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < i+1; j++) {
				if(j == 0) map[i][j] += map[i-1][j];	// 맨 왼쪽
				else if(j == i) map[i][j] += map[i-1][j-1];		// 맨 왼쪽
				else map[i][j] += Math.max(map[i-1][j-1], map[i-1][j]);
			}
		}
		
		int result = 0;
		for(int i = 0; i < N; i++) {
			result = Math.max(map[N-1][i], result);
		}
		
		// 정답
		System.out.println(result);
	}

}

 

 

2.  bottom up 접근 - 성공

뭔가 아쉬움을 느껴 다른 사람들의 풀이를 보다 bottom up으로 접근한 풀이가 보였다

이렇게 접근하니 if-else if-else로 나눈 내 방법도

현재 선택할 수 있는 두 값이 바로 보였다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [][] map = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < i+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = N-2; i >= 0; i--) {
			for(int j = 0; j <= i; j++) {
				map[i][j] += Math.max(map[i+1][j], map[i+1][j+1]);
			}
		}
		
		// 정답
		System.out.println(map[0][0]);
	}

}

 

 

 

이번 문제를 풀며 "생각의 전환"이 중요하다고 느꼈다