[Programmers] 정수삼각형 - Java

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

---

1. 문제

주어진 삼각형에서 합이 가장 클 때의 합을 반환한다.

2. 풀이

1차 : 각각의 위치 마다 위, 왼쪽 위를 검사하는 방식

2차 : 맨 왼쪽 줄, 맨 오른쪽 줄, 가운데로 나누어

맨 왼쪽 줄은 윗 녀석만 검사

맨 오른쪽 줄은 왼쪽 윗 녀석만 검사

가운데는 윗 녀석, 왼쪽 윗 녀석 둘 다 검사하는 방식이다.

 

1차 보다는 2차의 코드 가독성이 더 좋았다.

 

3. 코드

1차 -> 이중for문

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

class Solution {
    public int solution(int[][] triangle) {
        int ans = 0;
        int N = triangle.length;
        int[][] dp = new int[N][N];
        
        dp[0][0] = triangle[0][0];
        ans = dp[0][0];
        
        for (int i=1; i<N; i++) {
            for (int j=0; j<=i; j++) {
                if (j-1 >= 0) {
                    dp[i][j] = dp[i-1][j-1]+triangle[i][j];
                }
                if (dp[i-1][j] != 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j]+triangle[i][j]);
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        
        return ans;
    }
}

2차 -> 단일 for문

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

class Solution {
    public int solution(int[][] triangle) {
        int ans = 0;
        int N = triangle.length;
        int[][] dp = new int[N][N];
        
        dp[0][0] = triangle[0][0];
        ans = dp[0][0];
        
        for (int i=1; i<N; i++) {
            // 맨 왼쪽 줄
            dp[i][0] = dp[i-1][0] + triangle[i][0];
            
            // 맨 오른쪽 줄
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
            
            // 가운데
            for (int j=1; j< i; j++) {
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
        
        for (int i=0; i<N; i++) {
            ans = Math.max(ans, dp[N-1][i]);
        }
        
        return ans;
    }
}

 

4. 사담

문제를 풀었어도 이거 다시 짜라면 못짤 것 같은데? 싶은 코드는 지양하게 되는 것 같다.

알고리즘을 풀 때도 클린코드를 신경쓰면서 하자