-
99클럽 코테 스터디 21일차 TIL / 정수 삼각형(프로그래머스)Study(진행중)/항해99 2024. 8. 12. 00:37
오늘의 학습 키워드
- 알고리즘
- DP
공부한 내용 본인의 언어로 정리하기
https://school.programmers.co.kr/learn/courses/30/lessons/43105
dp를 이용해서 풀어야 하는 문제를 풀었다.
풀이 과정은 다음과 같다.
1. 처음 주어진 배열로부터 높이가 삼각형의 높이가 될 때 까지 진행
2. 높이를 하나씩 올려가며(i + 1) 이전 높이(i)의 위에 있는 두 숫자 중 큰 숫자를 채택
3. 채택한 숫자 + 입력으로 주어진 삼각형 숫자
4. 최대 높이 h에서 밑변의 값들을 비교하며 최대값을 갱신하면 가장 큰 숫자가 나옴
풀고 나서 다른 사람들 풀이를 보니, 내가 너무 문제 조건대로만 풀었다는 생각이 들었다.
다른 사람들의 경우 밑변 즉 h부터 0까지 반복문을 돌면서 dp 배열을 계산하는 것을 보았고, 이게 코드가 훨씬 깔끔했기에 하나를 또 배웠다.
풀이는 다음과 같다.
import java.util.*; class Solution { public int solution(int[][] triangle) { int h = triangle.length; int[][] dp = new int[h][]; for (int i = 0; i < h; i++) { dp[i] = new int[triangle[i].length]; Arrays.fill(dp[i], -1); } dp[0][0] = triangle[0][0]; for (int i = 1; i < h; i++) { int w = i + 1; for (int j = 0; j < w; j++) { dp[i][j] = triangle[i][j]; int max = -1; if (j - 1 != -1) max = dp[i - 1][j - 1]; if (j != w - 1) max = Math.max(max, dp[i - 1][j]); dp[i][j] += max; } } int max = -1; for (int i = 0; i < h; i++) { max = Math.max(max, dp[h - 1][i]); } return max; } }
반응형'Study(진행중) > 항해99' 카테고리의 다른 글
99클럽 코테 스터디 23일차 TIL / IPO(Leetcode) (0) 2024.08.14 99클럽 코테 스터디 22일차 TIL / Maximal Rectangle(Leetcode) (0) 2024.08.13 99클럽 코테 스터디 20일차 TIL / 섬 연결하기(프로그래머스) (0) 2024.08.11 99클럽 코테 스터디 19일차 TIL / 조이스틱(프로그래머스) (0) 2024.08.10 99클럽 코테 스터디 18일차 TIL / 일루미네이션(백준) (0) 2024.08.08