[Algorithm] ๐Ÿ“ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ •์ˆ˜ ์‚ผ๊ฐํ˜•

0. ๋ฌธ์ œ

์œ„์™€ ๊ฐ™์€ ์‚ผ๊ฐํ˜•์˜ ๊ผญ๋Œ€๊ธฐ์—์„œ ๋ฐ”๋‹ฅ๊นŒ์ง€ ์ด์–ด์ง€๋Š” ๊ฒฝ๋กœ ์ค‘, ๊ฑฐ์ณ๊ฐ„ ์ˆซ์ž์˜ ํ•ฉ์ด ๊ฐ€์žฅ ํฐ ๊ฒฝ์šฐ๋ฅผ ์ฐพ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์•„๋ž˜ ์นธ์œผ๋กœ ์ด๋™ํ•  ๋•Œ๋Š” ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์œผ๋กœ ํ•œ ์นธ ์˜ค๋ฅธ์ชฝ ๋˜๋Š” ์™ผ์ชฝ์œผ๋กœ๋งŒ ์ด๋™ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 3์—์„œ๋Š” ๊ทธ ์•„๋ž˜์นธ์˜ 8 ๋˜๋Š” 1๋กœ๋งŒ ์ด๋™์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

์‚ผ๊ฐํ˜•์˜ ์ •๋ณด๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด triangle์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๊ฑฐ์ณ๊ฐ„ ์ˆซ์ž์˜ ์ตœ๋Œ“๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ
์‚ผ๊ฐํ˜•์˜ ๋†’์ด๋Š” 1 ์ด์ƒ 500 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
์‚ผ๊ฐํ˜•์„ ์ด๋ฃจ๊ณ  ์žˆ๋Š” ์ˆซ์ž๋Š” 0 ์ด์ƒ 9,999 ์ดํ•˜์˜ ์ •์ˆ˜์ž…๋‹ˆ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก 2์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ dp ๊ตฌํ˜„ํ•จ
๐Ÿ’ก ๊ฐ€์žฅ ์™ผ์ชฝ, ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ, ์ค‘๊ฐ„์— ์žˆ๋Š” ๊ฒƒ ๊ตฌ๋ถ„ํ•ด์„œ ๊ณ„์‚ฐํ•˜๊ธฐ

2. ํ•ต์‹ฌ ํ’€์ด

  1. 2์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ dp ๊ตฌํ˜„ํ•จ
int length = triangle.length;
        
int[][] dp = new int[length][triangle[length-1].length];
  1. ๊ฐ€์žฅ ์™ผ์ชฝ, ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ, ์ค‘๊ฐ„์— ์žˆ๋Š” ๊ฒƒ ๊ตฌ๋ถ„ํ•ด์„œ ๊ณ„์‚ฐํ•˜๊ธฐ
if(j == 0){
	dp[i][j] = dp[i-1][j]+triangle[i][j];
} else if(j == i){
	dp[i][j] = dp[i-1][j-1]+triangle[i][j];
} else {
	dp[i][j] = Math.max(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
}

3. ์ฝ”๋“œ

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

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ