문제 출처

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105

문제 설명

삼각형 정보가 담긴 배열 triangle이 주어 질 때, 거쳐간 숫자의 최댓값을 return 하라.

ex) 3층에 8, 1, 0은
8은 3과 결합 할 수 있다.
1은 3 or 8과 결합 할 수 있다.
0은 8과 결합 할 수 있다.

해당 과정을 거쳐 가장 큰 값은 7 + 3 + 8 + 7 + 5 = 30 이다.

접근 방법

triangle 현재 위치와 이전 왼쪽 위치 or 이전 오른쪽 위치를 더하면서 더 큰 값을 채택한다.

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        for(int i =1; i<triangle.length; i++){
            for(int j = 0; j<triangle[i].length; j++){
                if(j == 0 ) triangle[i][j] += triangle[i-1][j]; // 왼쪽 끝
                else if(j == i) triangle[i][j] += triangle[i-1][j-1]; // 오른쪽 끝
                else triangle[i][j] += Math.max(triangle[i-1][j], triangle[i-1][j-1]);
            }
        }
        
        for(int k : triangle[triangle.length-1]){
            answer = Math.max(answer,k);
        }
        return answer;
    }
}

Review

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        // triangle을 순회 하며 초기화, i는 층, j는 위치
        for(int i = 1; i<triangle.length; i++){
            for(int j = 0; j<triangle[i].length; j++){
                // 가장 왼쪽
                if(j == 0) triangle[i][j] += triangle[i-1][j];
                    // 가장 오른쪽
                else if(j == i) triangle[i][j] += triangle[i-1][j-1];
                    // 평범한 경우
                else triangle[i][j] += Math.max(triangle[i-1][j], triangle[i-1][j-1]);
            }
        }
        for(int k : triangle[triangle.length-1]){
            answer = Math.max(k,answer);
        }
        return answer;
    }
}

Review2

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

public class 정수_삼각형 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N][N];

        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i<N; i++){
            for(int j = 0; j<=i; j++){
                if (j == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j];
                }else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j];
                }
                else{
                    dp[i][j] += Math.max(dp[i-1][j-1], dp[i-1][j]);
                }
            }
        }
        int MAX = Integer.MIN_VALUE;

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

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(MAX));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review3

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

public class 정수_삼각형_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int dp[][] = new int[N][N];

        StringTokenizer st;
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<i+1; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i<N; i++){
            for(int j=0; j<i+1; j++){
                if(j == 0){
                    dp[i][j]+=dp[i-1][j];
                } else if(j == i){
                    dp[i][j] += dp[i-1][j-1];
                } else{
                    dp[i][j] = Math.max(dp[i][j]+dp[i-1][j-1], dp[i][j]+dp[i-1][j]);
                }

            }
        }
        int Max = Integer.MIN_VALUE;
        for(int i = 0; i<N; i++){
            Max = Math.max(dp[N-1][i],Max);
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(Max));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

문제를 처음 풀 때, 너무 어렵게 생각하여 2중 list를 이용하여 현재 위치에서 다음 위치를 더했을 때, 경우 2가지를 저장하는 식으로 고안했으나 간단하게 triangle 배열 자체를 이용하면 되는 문제였다.
출처
https://velog.io/@co_ol/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95java

Review2
백준에 있어서 다시 풀게 되었다.
그럼에도 많이 해매었다.
설계를 잘 못하여 내려오면서 겹치는 부분은 비교하여 더 큰 수를 대입한다라는 큰 틀만 짜고, 아래에서 위에 것을 받게 코드를 구현해야하는데, 위에서 아래에 내려주는 형태로 코드를 구현하여 조금 복잡해져서 다시 풀었다.

더 열심히 해야겠다.

Review3
확실히 여러번 푼 문제라 금방 풀었다.

문제푼 흔적

Review

Review2

Review3