[프로그래머스]Lv.3 정수 삼각형

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

프로그래머스

---

문제

• 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 
• 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.
• 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
• 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예제

---

풀이방식

이번 문제는 DP를 사용하는 문제이다.

• 아직 공부하지 않은 부분이기에 일단은 '이런식으로 푼다' 정도만 알고 넘어가자.
• 코테 끝난 후에 다시 차근차근 공부할 것이다.

---

설계과정

1. 입력받은 값을 각각 2차원 배열과 트리로 표시해보면 아래 이미지와 같다.

 

2. 트리의 각 좌우 끝은 해당 수만 올 수 있으므로 경우의 수가 1이다. 그러므로 각 값들을 누적해서 배열에 넣는다.

 

1. 시간 복잡도를 줄이기 위해 제곱근을 사용하여 0으로 나누어 떨어지는 약수를 찾는다.

1. 시간 복잡도를 줄이기 위해 제곱근을 사용하여 0으로 나누어 떨어지는 약수를 찾는다.

 

• Math.sqrt() : 제곱근을 반환한다.
• 제곱근에 대해서는 아래 사이트를 참고해보자.

 

 

4. 아래 글을 참고하여 코딩하였다.

 

https://web2eye.tistory.com/163

프로그래머스 LEVEL 3 : 정수 삼각형 (DP)

---

풀이과정

1. 입력받은 값을 저장할 배열과 숫자를 누적시킬 배열을 만든다.

 

2. 입력받은 배열을 각각 2차원 배열과 트리로 표시해보면 아래 이미지와 같다.

triangle[ ][ ]

3. 트리의 각 좌우 끝 값들을 누적해서 copyTriangle 배열에 넣는다.

• 트리(triangle[ ][ ])의 각 좌우 끝은 해당 수 하나만 올 수 있으므로 경우의 수가 하나 뿐이다.
• 그러므로 각 수들을 누적해서 copyTriangle[ ][ ]에 넣는다.

4. copyTriangle[ ][ ] 배열의 왼쪽 끝 값을 구한다.

• 아래 예시를 통해 표가 채워지는 과정을 이해해보자.
• i = 1) copyTriangle[1][0] = copyTriangle[0][0] + triangle[1][0]  > copyTriangle[1][0]  = 7 + 3
• i = 2) copyTriangle[2][0] = copyTriangle[1][0] + triangle[2][0]  > copyTriangle[2][0]  = 10 + 8

5. copyTriangle[ ][ ] 배열의 오른쪽 끝 값을 구한다.

• 아래 예시를 통해 표가 채워지는 과정을 이해해보자.
• i = 1) copyTriangle[1][1] = copyTriangle[0][0] + triangle[1][1]  > copyTriangle[1][1]  = 7 + 8
• i = 2) copyTriangle[2][2] = copyTriangle[1][1] + triangle[2][2]  > copyTriangle[2][2]  = 15 + 0

6. 나머지 배열을 채우기 위해서 좌우 두 값을 비교하여 더 큰 값을 copyTriangle[ ][ ] 배열에 넣는다.

• Math.max() : 입력받은 두 개의 인자 중 큰 값을 리턴한다.
• 아래 예시를 통해 표가 채워지는 과정을 이해해보자.
• i = 2) copyTriangle[2][1] = Math.max(copyTriangle[1][0], copyTriangle[1][1]) + triangle[2][1]  = Math.max(10, 15) + 1 > 15 + 1

7. copyTriangle 배열의 맨 마지막 값들 중에서 최대값을 찾아 출력한다.

• copyTriangle 배열의 맨 마지막 값들이 해당 경로의 최대 값들을 의미한다.

---

답안소스

• 프로그래머스

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] triangle = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
        System.out.println(solution.solution(triangle));
    }
}

class Solution {
    public int solution(int[][] triangle) {
        int[][] copyTriangle = new int[triangle.length][triangle.length];
        
		copyTriangle[0][0] = triangle[0][0];
		
		for(int i=1; i<triangle.length; i++) {
			copyTriangle[i][0] = copyTriangle[i-1][0] + triangle[i][0];
			copyTriangle[i][i] = copyTriangle[i-1][i-1] + triangle[i][i];
		}
		
		for(int i=2; i<triangle.length; i++) {
			for(int j=1; j<i; j++) {
				copyTriangle[i][j] = Math.max(copyTriangle[i-1][j-1], copyTriangle[i-1][j]) + triangle[i][j];
			}
		}
		
		int max = copyTriangle[copyTriangle.length-1][0];
		for(int i=1; i<triangle.length; i++) {
			int tmp = copyTriangle[copyTriangle.length-1][i];
			
			if(max < tmp) {
				max = tmp;
			}
		}
		return max;
    }
}

---

• 이클립스

public class IntTriangle {

	public static int solution(int[][] triangle) {
		int[][] copyTriangle = new int[triangle.length][triangle.length];
        
		copyTriangle[0][0] = triangle[0][0];
		
		for(int i=1; i<triangle.length; i++) {
			copyTriangle[i][0] = copyTriangle[i-1][0] + triangle[i][0];
			copyTriangle[i][i] = copyTriangle[i-1][i-1] + triangle[i][i];
		}
		
		for(int i=2; i<triangle.length; i++) {
			for(int j=1; j<i; j++) {
				copyTriangle[i][j] = Math.max(copyTriangle[i-1][j-1], copyTriangle[i-1][j]) + triangle[i][j];
			}
		}
		
		int max = copyTriangle[copyTriangle.length-1][0];
		for(int i=1; i<triangle.length; i++) {
			int tmp = copyTriangle[copyTriangle.length-1][i];
			
			if(max < tmp) {
				max = tmp;
			}
		}
		return max;
	}
	
	public static void main(String[] args) {
		int[][] triangle = new int[][]{{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
		
		System.out.println(IntTriangle.solution(triangle));
	}
}