프로그래머스 정수 삼각형 주소
문제
삼각형의 꼭대기 부터 대각선으로만 움직여서 숫자를 더했을 때 가장 숫자가 큰 경우를 반환하라.
그림으로 간단히 요약하자면 아래 그림과 같다.
풀이
DFS로 아래 숫자를 하나씩 더해서 비교하는 방법과 DP로 푸는 방법이있다.
→ 난 DP로 풀었음.
삼각형의 세로 축이 진행 될때마다 세 가지 경우의 수가 나온다.
1.
dp[i][0]인 경우
•
각각 가로 줄의 첫 번째 숫자임. (7, 3, 8, 2, 4)
2.
dp[i][i]인 경우
•
각각 가로 줄의 마지막 숫자임. (7, 8, 0, 4, 5)
3.
dp[i][1 ~ i - 1]인 경우
•
1번과 2번을 제외한 나머지 숫자임. (1, 7, 4, 5, 2, 6)
즉 삼각형의 세로 축을 순회하면서
•
1 번과 2 번의 경우는 바로 윗 숫자를 더해서 내려오면 된다.
•
3번의 경우 윗 숫자 중 큰 숫자와 현재 숫자를 더해서 내려오면 된다.
•
DP 2차원 배열이 만들어지면 가장 아랫 줄에서 가장 큰 값을 반환하면 정답이다.
구현
package 프로그래머스.정수삼각형;
public class Main {
public static void main(String[] args) {
// triangle 2차원 배열
int[][] arr = {
{7},
{3, 8},
{8, 1, 0},
{2, 7, 4, 4},
{4, 5, 2, 6, 5}};
new Solution().solution(arr);
}
}
// 정답
class Solution {
public int solution(int[][] triangle) {
int heigth = triangle.length;
int answer = 0;
어차피 삼각형 부분만 사용할 것이기 때문에 height * height으로 배열을 만들어준다.
int[][] dp = new int[heigth][heigth];
삼각형의 꼭대기 값을 초기화한다.
dp[0][0] = triangle[0][0];
삼각형의 세로를 순회한다.
for (int i = 1; i < heigth; i++) {
// 1번 케이스.
// 지금까지 더해온 숫자 + 삼각형의 현재 숫자
dp[i][0] = dp[i - 1][0] + triangle[i][0];
// 3번 케이스.
// 지금까지 더해 온 바로 윗 숫자 두개 중 큰 숫자 + 삼각형의 현재 숫자
for (int j = 1; j <= i; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
}
// 2번 케이스.
// 지금까지 더해온 숫자 + 삼각형의 현재 숫자.
dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
}
// DP의 마지막 줄에서 가장 큰 수를 도출.
for (int i = 0; i < heigth; i++)
answer = Math.max(dp[heigth - 1][i], answer);
// 반환
return answer;
}
}
Java
복사
