LEVEL 3 : 정수 삼각형

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

• 문제

  • 

    문제

---

풀이

• DP를 활용한 간단한 문제이다.
• dp 2차원 배열을 선언 후 dp [0][0]에 초깃값을 넣어준다
  • 2번째 줄부터는 DP를 활용하면 된다.
  • 1열 = 이전 행에 첫번째 요소에 값 밖에 못 더해준다.
  • 2열 ~ n -1 열 = 이전행의 i-1, i 번째 열 중 큰 값에 현재 값을 더해준다
  • n열 = 이전행의 마지막 열을 요소 값 밖에 못 더해준다. 
•  

• public static int solution(int[][] triangle) {
          int answer = 0;
          int[][] dp = new int[triangle.length][];// 계산된 배열
          dp[0] = new int[1];//초깃값
          dp[0][0] = triangle[0][0];
          for(int i=1;i<triangle.length;++i) {
          	dp[i] = new int[triangle[i].length];
          	dp[i][0] = dp[i-1][0] + triangle[i][0];//첫번째 열
          	for(int j=1;j<triangle[i].length-1;++j) {//2열 ~ n-1열
          		dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
          	}
          	dp[i][triangle[i].length-1] = triangle[i][triangle[i].length-1] + dp[i-1][triangle[i-1].length-1];
              //n 열
          }
          for(int i=0;i<triangle[triangle.length-1].length;++i) {
          	answer = Math.max(answer, dp[dp.length-1][i]);//최댓값을 구해준다
          }
          return answer;
      }