정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
dp[i][0]은 좌표 이동 루트가 다르므로 예외처리 해주고 나머지는 같은 로직으로 반복
단, 거쳐간 숫자의 최대 합을 구해야하므로 (현재 위치한 숫자 + 대각선 위 왼쪽과 오른쪽 각각의 값) 비교해주고 더 큰 값만 dp에 저장해주면 된다.
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
int answer = 0;
int len = triangle.length;
int dp[][] = new int [len][len];
dp[0][0] = triangle[0][0]; //7
for(int i = 1; i < len; i++){
dp[i][0] = dp[i-1][0] + triangle[i][0];
for(int j = 1; j <= i; j++){
dp[i][j] = Math.max(dp[i-1][j] + triangle[i][j], dp[i-1][j-1] + triangle[i][j]);
}
}
for(int i = 1; i < dp.length; i++){
answer = Math.max(answer, dp[len-1][i]);
}
return answer;
}
}
'Algorithms > programmers' 카테고리의 다른 글
[이분탐색] 징검다리 건너기 (0) | 2024.01.23 |
---|---|
[이분탐색] 프로그래머스 입국심사 (0) | 2024.01.11 |
[Greedy] 프로그래머스 체육복, 큰 수 만들기, 구명보트, 단속카메라 (1) | 2023.12.28 |
[DFS/BFS] 프로그래머스 타겟넘버, 네트워크 (1) | 2023.12.22 |
[완전탐색] 프로그래머스 최소직사각형 (0) | 2023.12.01 |