BEAKJOON / 백준 - JAVA 1932번 정수 삼각형

2024.08.25기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 dp를 이용해 한 칸 씩 내려갈 때 마다 수를 더 해 마지막 칸에서 가장 큰 값을 가지고 있는 수를 출력하는 문제입니다.

 

예제를 통해서 문제를 풀어 나가도록 하겠습니다.

// 예제
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

1. dp에 초기 맨 꼭대기 층을 먼저 입력해줍니다.

List<Integer>[] list = new LinkedList[n + 1];

// 꼭대기 층을 먼저 넣어 줍니다.
list[0] = new LinkedList<>();
list[0].add(0);
list[1] = new LinkedList<>();
list[1].add(Integer.parseInt(br.readLine()));

 

2. 맨 꼭대기 층에서 2번째 층 부터 dp를 이용해 윗 층을 참조해 더 해 나가면서 값을 저장해 줍니다.

1. 0번째 인덱스는 윗층에 0번째 인덱스만 참조하게 됩니다.
2. 0과 마지막 인덱스를 제외한 나머지 인덱스는 자기 자신의 인덱스와 (자신의 인덱스 - 1)을 참조하게 됩니다.
3. 마지막 인덱스는 윗층의 마지막 인덱스만 참조하게 됩니다.

int num;
StringTokenizer st;
for (int i = 2; i <= n; i++) {
    list[i] = new LinkedList<>();

    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < i; j++) {
        num = Integer.parseInt(st.nextToken());

        if (j == 0) { // 첫 번째는 윗 층의 첫 번째 칸만 연결되어 있습니다.
            list[i].add(list[i - 1].get(0) + num);
        } else if (j == i - 1) { // 마지막 칸은 윗 층의 마지막 칸만 연결되어 있습니다.
            list[i].add(list[i - 1].get(list[i - 1].size() - 1) + num);
        } else { // 중간에 있는 칸들은 윗 층의 현재 자신의 인덱스와 인덱스 -1 랑 연결되어 있습니다.
            list[i].add(Math.max(list[i - 1].get(j - 1), list[i - 1].get(j)) + num);
        }
    }
}

 

3. 이렇게 계산된 dp를 이용해 1층에 있는 값들 중 가장 큰 값을 출력하게 됩니다.

// 계속 더 해진 수에서 마지막 1층 중 가장 큰 값을 출력해줍니다.
int max = 0;
for (int i = 0; i < list[n].size(); i++) {
    max = Math.max(max, list[n].get(i));
}

 

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine()); // 삼각형의 크기
		
		List<Integer>[] list = new LinkedList[n + 1];
		
		// 꼭대기 층을 먼저 넣어 줍니다.
		list[0] = new LinkedList<>();
		list[0].add(0);
		list[1] = new LinkedList<>();
		list[1].add(Integer.parseInt(br.readLine()));
		
		int num;
		StringTokenizer st;
		for (int i = 2; i <= n; i++) {
			list[i] = new LinkedList<>();
			
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < i; j++) {
				num = Integer.parseInt(st.nextToken());
				
				if (j == 0) { // 첫 번째는 윗 층의 첫 번째 칸만 연결되어 있습니다.
					list[i].add(list[i - 1].get(0) + num);
				} else if (j == i - 1) { // 마지막 칸은 윗 층의 마지막 칸만 연결되어 있습니다.
					list[i].add(list[i - 1].get(list[i - 1].size() - 1) + num);
				} else { // 중간에 있는 칸들은 윗 층의 현재 자신의 인덱스와 인덱스 -1 랑 연결되어 있습니다.
					list[i].add(Math.max(list[i - 1].get(j - 1), list[i - 1].get(j)) + num);
				}
			}
		}
		
		// 계속 더 해진 수에서 마지막 1층 중 가장 큰 값을 출력해줍니다.
		int max = 0;
		for (int i = 0; i < list[n].size(); i++) {
			max = Math.max(max, list[n].get(i));
		}
		
		bw.write(Integer.toString(max));
		bw.flush();
		bw.close();
		br.close();
	}
}