[백준 / 실버1] 1932 정수 삼각형 (Java)

문제 보기

사용한 것

• 0과 1의 출력 횟수를 구하기 위한 bottom-up

풀이 방법

• 입력 받으면서 왼쪽 대각선으로 바로 위의 인덱스와 더해서 갱신하고, 그 다음 오른쪽 대각선으로 바로 위의 인덱스와 더한 것을 왼쪽 대각선으로 더한 값과 비교해서 갱신

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dArr = new int[N][N];
        dArr[0][0] = Integer.parseInt(br.readLine());
        for(int i = 1; i < N; i++) {
            int[] arr = Stream.of(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

            for(int j = 0; j < i; j++) {
                dArr[i][j] = arr[j] + dArr[i - 1][j];
            }

            for(int j = 0; j < i; j++) {
                dArr[i][j + 1] = Math.max(dArr[i - 1][j] + arr[j + 1], dArr[i][j + 1]);
            }
        }

        int answer = dArr[N - 1][0];
        for(int i = 1; i < N; i++) {
            answer = Math.max(dArr[N - 1][i], answer);
        }

        System.out.println(answer);
    }
}