[백준] 1932번: 정수 삼각형 | C++ 풀이

# 문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

이미지를 클릭하면 백준 문제 페이지로 이동합니다.

 

 

---

 

# 풀이

지난 번에 DP 찍먹을 해봤다면 이번에는 아주아주 조금 더 심화!

내 생각엔 언제나 DP로 구현하기 <<<< DP로 풀어야 함을 떠올리기인 것 같다.

 

다시 한 번 짚어보자면 DP로 문제를 풀 땐 해당 문제가 작은 문제들로 나누어지는지, 그 작은 문제들이 반복되어 나타나고/사용되고 있는지를 먼저 확인해야 한다. 이번 문제는 가장 꼭대기에서부터 현재 자리까지의 최대합 구하기로 문제가 나누어지고, 그 문제들을 반복 사용해 결과를 낼 수 있으므로 DP로 풀기 적합! 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;

    int input[502][502] = {}; // 정수 삼각형 선언 및 입력받기
    for(int i = 1; i < n+1; i++){ // line: 1부터 시작
        for(int j = 1; j < i+1; j++){ // index: 1부터 시작
            cin >> input[i][j];
        }
    }

    int D[502][502] = {}; // DP 테이블 생성 및 초기값 할당
    D[1][1] = input[1][1]; // 가장 꼭대기 값

    for(int i = 2; i < n+1; i++){
        for(int j = 1; j < i+1; j++){
            D[i][j] = max(D[i-1][j-1], D[i-1][j]) + input[i][j];
        }
    }

    int res = D[n][1]; // 마지막 줄에서 가장 큰 값을 찾아 출력하기
    for(int i = 2; i < n+1; i++){
        res = max(res, D[n][i]);
    }
    cout << res;

    return 0;
}

 

부분적으로 코드를 나눠 살펴보도록 하자.

 

 

int input[502][502] = {}; // 정수 삼각형 선언 및 입력받기
for(int i = 1; i < n+1; i++){ // line: 1부터 시작
    for(int j = 1; j < i+1; j++){ // index: 1부터 시작
        cin >> input[i][j];
    }
}

 

우선 정수 삼각형을 입력받을 2차원 배열을 생성, 반복문을 통해 받아왔다.

앞으로 삼각형 속 숫자들을 부를 때 n번째 줄, m번째 인덱스라고 표현해줄 건데 헷갈리지 않게 line과 Index모두 1부터 시작해주었다. 그리고 뒤에서 분기를 나누지 않고 max 함수를 적용하기 위함도 있음! (뒤에서 마저 설명하겠습니다...)

더 나아가 삼각형의 크기는 1부터 500까지이므로 한칸 여유줘서 배열의 크기는 502로 설정!

 

 

int D[502][502] = {}; // DP 테이블 생성 및 초기값 할당
D[1][1] = input[1][1]; // 가장 꼭대기 값

for(int i = 2; i < n+1; i++){
    for(int j = 1; j < i+1; j++){
        D[i][j] = max(D[i-1][j-1], D[i-1][j]) + input[i][j];
    }
}

 

DP 테이블 또한 정수 삼각형 배열과 동일한 크기로 설정하고, 우리가 바로 알 수 있는 가장 꼭대기 값을 초기값으로 할당해주었다.

입력 예시 속 정수 삼각형에서는 7에 해당하는 값이다.

 

그 다음은 for문을 돌며 bottom-up 방식으로 DP 테이블을 채워준다.

1층 1번 인덱스에는 꼭대기값을 할당해주었으므로, 2층 1번 인덱스부터 시작한다. for문 속 조건문 설정에 주의하자.

 

처음엔 ① 왼쪽 가장자리를 따라 내려오는 n층 1번 인덱스의 값 ② 오른쪽 가장자리를 따라 내려오는 n층 n번째 인덱스의 값 ③ 두 가지 값을 비교해 더 큰 값을 선택해야 하는 중간 값 세 가지로 분기를 나눠 DP 테이블을 채워주었다.

근데... 인덱스 1, 1로 시작하고 초기화만 잘 해줬다면 굳이 분기를 안 나눠도 괜찮을 것 같더라고요? max 값 구하는 거니까 사용 안 한 0으로 초기화된 값이랑 정수 값이 있는 곳이랑 비교하면 당연히 max 값은 정수값이 있는 부분이잖아!

 

따라서 나눠둔 분기를 삭제하고, 모두 왼쪽 위의 값과 오른쪽 위의 값을 비교해 더 큰 값을 구하고 그 값과 해당 자리 input 값과 더해 현재 input 위치까지의 합을 DP 테이블에 저장해주었다. 인덱스가 헷갈린다면 입출력 예시에 왼쪽 정렬된 정수삼각형을 확인해보면 된다.

 

 

int res = D[n][1]; // 마지막 줄에서 가장 큰 값을 찾아 출력하기
for(int i = 2; i < n+1; i++){
    res = max(res, D[n][i]);
}
cout << res;

 

for문을 돌고 나면 DP테이블의 모든 자리에는 내 자리까지의 최대 합이 저장되어 있다.

따라서 마지막 줄, 입력 5의 정수 삼각형이라면 다섯 번째 줄에서 최대합을 찾아 해당 결과를 출력해주면 끝이다. (이번에도 인덱스에 주의하자)

 

 

 

배열 동적할당을 이용하면 메모리를 더 줄일 수 있을 것 같은데 굳이 싶어서 시도해보진 않았다 (〃⌒▽⌒〃)ゝ 

 

 

 

---

 

 

 

 

1932번: 정수 삼각형