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

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

문제

설명

삼각형 내에 정수들이 있다

맨 위층에서 한 칸씩 내려오면서 하나씩 더해 나올 수 있는 최대값을 반환하면 된다

단 다음 정수는 왼쪽 대각선 아래 or 오른쪽 대각선 아래다

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
백준 1932 정수 삼각형
n의 높이인 삼각형이 있다 상단부터 바닥까지 한 층에 하나의 수를 더해서 최대값 반환
그런데 대각선 왼/오른쪽에 위치한 숫자만 선택 가능
입력과 동시에
메모이제이션 배열에 더하면서 기록
Math.max() 함수로 비교
 */
public class cote {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 메모이제이션용 배열
    static int[][] dp;

    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(br.readLine());

        // 일부러 양옆에 한칸씩 추가함 0으로 둘거임 비교를 쉽게하기 위해
        dp = new int[n][n + 2];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 첫 칸, 마지막 칸 비워줌
            for (int j = 1; j < i + 2; j++) {
                dp[i][j] += Integer.valueOf(st.nextToken());

                // 첫 줄을 제외하고 나머지 줄은 그 전줄의 좌/우 수 중 더 큰수를 더해줌
                if (i != 0) {
                    dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
            }
        }

        bw.write(Arrays.stream(dp[n - 1]).max().getAsInt() + "");
        bw.flush();
        bw.close();
    }
}

dp 문제다

dp식으로 메모이제이션 배열을 선언해 풀어보았다

그런데 양쪽 삼각형의 모서리에 위치한 정수들의 값을 가져오기가 까다롭다

조건문으로 0번째 값이면, 마지막 값이라면... 이런걸 넣어줘야 하니까

그래서 그냥 배열의 앞 뒤로 한칸씩 더 넣어줘버렸다

그래서 배열의 초기값을 0으로 초기화되니까 값 비교하기도 편해졌다

배열의 출력 시의 모습

https://github.com/qTeTp/Algo/tree/main/%EB%B0%B1%EC%A4%80/Silver/1932.%E2%80%85%EC%A0%95%EC%88%98%E2%80%85%EC%82%BC%EA%B0%81%ED%98%95

Algo/백준/Silver/1932. 정수 삼각형 at main · qTeTp/Algo