[프로그래머스] lv3. 정수 삼각형 [#DP]

 

 

 

오늘은 알고리즘 스터디에서 처음으로 등장한 lv3 문제!

정수 삼각형을 들고 왔다!

 

그동안 그래프 문제에 익숙해져있던 나는

배열 형식으로 되어있는 연결 그래프는 어떻게 풀까 고민을 잠깐했다.

 

그러나 규칙을 알면 지금까지 풀었던 문제들보다 넘나 쉬워진다.

 

그 문제 지금부터 고고싱!

 

---

1. 문제 출처

---

 

 

프로그래머스

 

 

 

---

2. 설계

---

 

 

위 사진은 문제의 대표 예제이다.

이 예제를 기준으로 규칙을 찾아보자!!

 

 

 

1. 부모의 왼쪽자식과 오른쪽자식을 찾는 규칙

 

위 그림에서 자식을 찾는 규칙을 보면 아래와 같은 규칙이 있다.

 

• 자신의 왼쪽 자식은 [+1 , 0] 증가
• 자신의 오른쪽 자식은 [+1, +1] 증가

 

그래서 (0,0) 위치에 있는 7의 경우 왼쪽 자식은 [0+1, 0]을 증가시켜 [1,0] 이라는 사실을 알 수 있다.

또한 오른쪽 자식은 [0+1, 0+1]을 증가시켜 [1,1]이라는 사실을 알 수 있다.

 

 

2. 가장 아래까지 가장 큰 수를 저장하는 법

 

dp 이중 배열이 있다고 가정한다. dp에는 각 위치에서 가질 수 있는 가장 큰 수를 의미한다.

 

그러면 (0,0) 인 7에서는 가장 큰 수로 7을 가질 수 있다. 이 값은 가장 윗 값, 처음 값이므로 dp 초기값으로 두고 시작한다. 

public int solution(int[][] triangle) {
        
	int r = triangle.length;
	int c = triangle[r-1].length;
        
	int[][] dp = new int[r][c];
	dp[0][0] = triangle[0][0];
}

 

 

1번에서 왼쪽 자식과 오른쪽 자식을 찾는 방법을 알았기 때문에 내 위치에서 왼쪽 자식과 오른쪽 자식이 가질 수 있는 최대 수를 계산해주면 된다.

 

왼쪽자식 (1,0)은 dp[1][0] = 0이므로 부모 값 (7) + 현재 자식값 (3) = 10이 가장 큰 값이다. ==> dp[1][0] = 10으로 갱신

왼쪽자식 (1,1)은 dp[1][1] = 0이므로 부모 값 (7) + 현재 자식값 (8) = 15이 가장 큰 값이다. ==> dp[1][1] = 15으로 갱신

 

이런식으로 계산해주다가 dp에 이미 최대값이 들어가있는데, 추가적으로 또 최대값이 갱신되어야할 때가 있을 것이다. 바로 (2,1)와 같은 위치를 말한다.

 

 

(2,1)은 자신의 부모 (1,0)의 dp[1][0] = 10에 기록되어있던 값과 자신(1)을 더해 11이라는 수를 dp에 저장했다.

==> dp[2][1] = 10

 

근데 (2,1)은 부모가 2명이다. 그래서 (1,1)에서도 (2,1)은 왼쪽 자식으로 접근할 수 있다.

또 다른 부모 dp[1][1] = 15에 기록되어있던 값과 자신(1)을 더해 16이라는 수를 만들 수 있다.

이 때 이미 dp[2][1] = 10이라고 저장되어 있는 값보다 새로 온 값이 더 큰 경우 갱신해주면 된다.

 

for(int i=0;i<r-1;i++){
	for(int j=0;j<triangle[i].length;j++){
		int leftC = j;
		int rightC = j+1;
               
		//좌측 dp 구하기
		int newLeftNum = triangle[i+1][leftC] + dp[i][j];
		dp[i+1][leftC] = Math.max(dp[i+1][leftC], newLeftNum);
                
		//우측 dp 구하기
		int newRightNum = triangle[i+1][rightC] + dp[i][j];
		dp[i+1][rightC] = Math.max(dp[i+1][rightC], newRightNum);
	}
}//i for end

 

위 설계의 코드이다. 이 때 주의할 점은 i for의 경우 맨 아래 줄 까지 내려가면 안된다는 것이다.

왜냐하면 맨 아래 줄은 자식이 없기 때문이다.

 

 

3. 결과 도출

결과는 dp의 맨 아래줄 중 가장 큰 값이 결과이다.

//dp 마지막 줄에서 제일 큰 수가 정답
int result = 0;
for(int i=0;i<c;i++){
	result = Math.max(result,dp[r-1][i]);
}

 

 

 

 

---

3. 전체 코드

---

//무조건 삼각형
class Solution {
    public int solution(int[][] triangle) {
        
        int r = triangle.length;
        int c = triangle[r-1].length;
        
        int[][] dp = new int[r][c];
        dp[0][0] = triangle[0][0];
        
        for(int i=0;i<r-1;i++){
            for(int j=0;j<triangle[i].length;j++){
                int leftC = j;
                int rightC = j+1;
               
                //좌측 dp 구하기
                int newLeftNum = triangle[i+1][leftC] + dp[i][j];
                dp[i+1][leftC] = Math.max(dp[i+1][leftC], newLeftNum);
                
                //우측 dp 구하기
                int newRightNum = triangle[i+1][rightC] + dp[i][j];
                dp[i+1][rightC] = Math.max(dp[i+1][rightC], newRightNum);
            }
        }//i for end
        
        //dp 마지막 줄에서 제일 큰 수가 정답
        int result = 0;
        for(int i=0;i<c;i++){
            result = Math.max(result,dp[r-1][i]);
        }
        
        return result;
    }
}

 

전제 조건으로 무조건 삼각형 형태가 나온다고 했으므로 한 부모에게 무조건 left, right 자식이 있다고 생각해서 경계조건을 설정하지 않았다.