[동적계획법] 정수삼각형

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

|| 문제설명 ||

1. 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 한다.
2. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다.
3. 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 작성하라.

int [][] triangle : 삼각형의 정보가 담긴 2차원 배열

- 삼각형의 높이 : 1 이상 500 이하
- 삼각형을 이루고 있는 숫자 : 0 이상 9,999 이하, 정수

---

|| 문제해결과정 ||

1) DP : O(n^2)

---

|| 코드 ||

가장 효율적인 코드

[2021.01.26]

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
	        
	        for(int i=1; i<triangle.length; i++) {
	            for(int j=0; j<triangle[i].length; j++) {
	            	if(j == 0) triangle[i][j] += triangle[i-1][j];
	            	else if(j == triangle[i].length - 1) triangle[i][j] += triangle[i-1][j-1];
	            	else triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
	            	if(i == (triangle[i].length - 1) && triangle[i][j] > answer) answer = triangle[i][j];
	            }
	        }
	        return answer;
    }
}

---

[2021.01.26]

- 시간복잡도를 줄이는 방법은 무엇이 있을까
- 모든 O(n^2)동안 한 번씩 거쳐갈 if(i == (triangle[i].length - 1) && triangle[i][j] > answer) answer = triangle[i][j]; 이 코드를 따로 빼준다면 어떠한 변화가 있을까

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
	        
	        for(int i=1; i<triangle.length; i++) {
	            for(int j=0; j<triangle[i].length; j++) {
	            	if(j == 0) triangle[i][j] += triangle[i-1][j];
	            	else if(j == triangle[i].length - 1) triangle[i][j] += triangle[i-1][j-1];
	            	else triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
	            	
	            }
	        }
	        for(int i=0; i<triangle[triangle.length-1].length; i++) {
	        	if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
	        }
	        return answer;
    }
}

for문 밖으로 빼고 돌렸을 때 대체적으로 전보다 줄어든 결과를 눈으로 확인할 수 있다.

하지만 효율성 테스트 8번, 9번, 10번과 같이 특수한 경우(?)에서는 오히려 비효율적이다.

---

[2021.01.26]

- for문의 조건문을 for문 3개로 나눴을 경우

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for(int i=1; i<triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
        }
        for(int i=1; i<triangle.length; i++) {
            triangle[i][triangle[i].length - 1] += triangle[i-1][triangle[i].length - 2];
        }
	        
	for(int i=1; i<triangle.length; i++) {
	    for(int j=1; j<triangle[i].length-1; j++) {
	    	triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];        	
	        }
	    }
	for(int i=0; i<triangle[triangle.length-1].length; i++) {
	    if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
        }	        
        return answer;
    }
}

위와 같이 특수한 경우 빼고 시간복잡도가 현저히 줄어들었다.

특수한 경우가 대체 무슨 경우가 있을 까!

지금까지 다른 차이점이라고는 for문의 내용 → for문의 개수가 최소한이어야하고 그 안의 내용도 최소가 되어야한다.

---

[2021.01.27]

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for(int i=1; i<triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][triangle[i].length - 1] += triangle[i-1][triangle[i].length - 2];
        }
	for(int i=1; i<triangle.length; i++) {
	    for(int j=1; j<triangle[i].length-1; j++) {
	     	triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];           	
	    }
	}
	for(int i=0; i<triangle[triangle.length-1].length; i++) {
	    if(triangle[triangle.length-1][i] > answer) answer = triangle[triangle.length-1][i];
        }	        
        return answer;
    }
}

[효율성]

- 중복for문: O(n^2) < for문: O(2) + 중복for문: O((n-2)^2)

- for문: O(1) + for문: O(1) < for문: (2)

결론은 for문은 적을 수록 좋지만 for문을 추가하더라도 중복for문의 내용물을 줄이는게 가장 효율적이다.