์์ ๊ฐ์ ์ผ๊ฐํ์ ๊ผญ๋๊ธฐ์์ ๋ฐ๋ฅ๊น์ง ์ด์ด์ง๋ ๊ฒฝ๋ก ์ค, ๊ฑฐ์ณ๊ฐ ์ซ์์ ํฉ์ด ๊ฐ์ฅ ํฐ ๊ฒฝ์ฐ๋ฅผ ์ฐพ์๋ณด๋ ค๊ณ ํฉ๋๋ค. ์๋ ์นธ์ผ๋ก ์ด๋ํ ๋๋ ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ํ ์นธ ์ค๋ฅธ์ชฝ ๋๋ ์ผ์ชฝ์ผ๋ก๋ง ์ด๋ ๊ฐ๋ฅํฉ๋๋ค. ์๋ฅผ ๋ค์ด 3์์๋ ๊ทธ ์๋์นธ์ 8 ๋๋ 1๋ก๋ง ์ด๋์ด ๊ฐ๋ฅํฉ๋๋ค.
์ผ๊ฐํ์ ์ ๋ณด๊ฐ ๋ด๊ธด ๋ฐฐ์ด triangle์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๊ฑฐ์ณ๊ฐ ์ซ์์ ์ต๋๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์ธ์.
์ ํ์ฌํญ
์ผ๊ฐํ์ ๋์ด๋ 1 ์ด์ 500 ์ดํ์ ๋๋ค.
์ผ๊ฐํ์ ์ด๋ฃจ๊ณ ์๋ ์ซ์๋ 0 ์ด์ 9,999 ์ดํ์ ์ ์์ ๋๋ค.
๐ก 2์ฐจ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ dp ๊ตฌํํจ
๐ก ๊ฐ์ฅ ์ผ์ชฝ, ๊ฐ์ฅ ์ค๋ฅธ์ชฝ, ์ค๊ฐ์ ์๋ ๊ฒ ๊ตฌ๋ถํด์ ๊ณ์ฐํ๊ธฐ
int length = triangle.length;
int[][] dp = new int[length][triangle[length-1].length];
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];
}
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;
}
}
์ฑ๊ณตโจ