[백준(BOJ)] 1932번 정수 삼각형 C++

문제 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

어떤 문제인가?

삼각형의 맨 위부터 대각선으로 이동하며 맨 밑으로 내려왔을 때, 지나온 수들의 합이 최대가 되도록 했을 때 그 합을 출력하는 문제이다.

 

 

접근 방법

나는 삼각형을 위에서 아래로가 아닌, 밑에서 위로 올라가면서 합이 최대가 되는 경로를 살펴볼 것이다.

 

int triangle[501][501];

입력을 저장할 이차원 배열을 선언해준다.

n이 500까지 입력될 수 있으므로 이에 맞게 배열의 크기를 설정해준다.

 

 

 

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        cin >> triangle[i][j];
    }
}

삼각형의 수들을 입력받는다.

 

for (int i = n; i > 0; i--) {
    for (int j = 0; j < i; j++) {
        int big = max(triangle[i][j],triangle[i][j+1]);
        triangle[i-1][j]+= big;
    }
}

이제 삼각형을 밑에서부터 위로 올라갈 것이다.

그리고 같은 층 j번째와 j+1번째 값을 비교해 더 큰 값을 한 칸 위층 j 번째 인덱스에 더해준다.

 

 

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

 

문제의 예시로 보자.

맨 밑층부터 시작.

4와 5 중 더 큰 5를 2에 더하기.

5와 2 중 더 큰 5를 7에 더하기.

2와 6 중 더 큰 6을 4에 더하기.

6과 5 중 더 큰 6을 4에 더하기.

             

그럼 삼각형은

        7
      3    8
   8    1    0
7    12    10   10

와 같은 모습으로 바뀔 것이다.

위 과정을 반복하면 삼각형의 꼭대기의 최댓값이 저장되어있을 것이다.

 

cout << triangle[1][1];

이차원 배열의 [ 1 ][ 1 ]을 출력해주면 끝!

 

 

무엇이 어려웠는가?

처음엔 문제에서 시키는대로 위에서 아래로 내려가는 방법을 생각해봤다.

아무리 생각해봐도 메모이제이션을 어떻게 해야할지 모르겠었다.

그래서 밑에서부터 위로 올라가는 방법을 생각했다.

이 방법이 맞다는 것을 알았고, 이 뒤로는 간단한 구현을 하여 문제를 풀 수 있었다.

 

 

배운 점

문제에서 설명하는 방식에 집착하지말자...

접근법은 달라도 문제해결에 도달할 수 있는 방법이 있을 수도 있다..

 

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/1932.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.