백준 1932번 C++ 정수 삼각형

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

처음에 문제를 잘못 이해하고 두 수 중 최대인 것을 골라 아래로 내려오는 건 줄 알았다.

그래서 1차원 배열로 풀고 뿌듯해하다가 다시 읽어보니 아예 아닌 문제 ㅋㅋㅋㅋ

그리고나서 처음 짠 코드가 다음과 같다.

#include <iostream>
#include <algorithm>
 
using namespace std;
int main() {
    int n;
    cin >> n;
 
    int** tri = new int*[n];
    for (int i = 0; i < n; i++) {
        tri[i] = new int[i];
        for (int j = 0; j <=i; j++) {
            cin >> tri[i][j];
        }
    }
 
    int max_sum = 0;
    if (n == 1) {
        max_sum = tri[0][0];
    }
    else {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    tri[i][j] += tri[i - 1][j];
                }
                else if (j == i) {
                    tri[i][j] += tri[i - 1][j - 1];
                }
                else {
                    tri[i][j] += max(tri[i - 1][j - 1], tri[i - 1][j]);
                }
            }
        }
 
        max_sum = tri[n-1][0];
        for (int i = 0; i < n; i++) {
            if (max_sum < tri[n - 1][i]) {
                max_sum = tri[n - 1][i];
            }
        }
 
        cout << max_sum;
    }
    return 0;
}

처음에 짠 코드를 보면 진짜 문제 그대로 해석했다는 걸 알 수 있다.

0

00

000

0000

00000

결과는

...

이후로도 뭐가 문제일까 잘 모르겠어서 조금씩 바꿔보았지만 결과는 런타임 에러X3

결국 주위에 도움을 요청했더니 2차원 배열 동적 할당이 문제인 것 같다고 했다.

그리고 나처럼 저렇게 딱딱 맞게 짜면 예외 처리를 해줘야 하는 번거로움도 있고 오류날 가능성도 많다고...

알고리즘 스터디 시작하고 많이 알아가는 것 같다.

000000

010000

012000

012300

012340

000000

이런 식으로 감싸주면 훨씬 편하다고 한다.

그래서 또 2차원 배열 동적 할당하고 초기화시켜줬더니 아예 코드가 돌아가질 않아서 그냥 검색해봤다.

애초에 배열 크기를 최대로 선언해주고 초기화한 다음 풀면 되는 거였다...

배열 선언이 문제였던 것이다. 왜 동적 할당으로 풀면 런타임 에러가 나는 걸까? 이유가 궁금하다.

그리고 리눅스에서 gcc로 정적으로 선언이 가능한데 vs에서는 왜 안 되는 걸까

아무튼 주위의 도움+검색으로 풀 수 있었다.

#include <iostream>
#include <algorithm>
 
using namespace std;
int tri[502][502] = { 0, };
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> tri[i][j];
        }
    }
 
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j <= i; j++) {
            tri[i][j] += max(tri[i - 1][j - 1], tri[i - 1][j]);
        }
    }
 
    int max = 0;
    for (int i = 1; i < n + 2; i++) {
        if (max < tri[n][i]) {
            max = tri[n][i];
        }
    }
 
    cout << max;
 
    return 0;
}

이 맛에 푸는 것 같다.

이게 동적 계획법이라는 건 검색하고 안 것이다. 동적 계획법 진짜 처음 들어봤다.

다른 사람들이 dp거리는 건 듣긴 했는데 그게 dynamic programming이었구나

알고리즘 스터디 시작하고 느낀 것은... '좀 더 일찍 시작할 걸'이었다.

그래도 파이썬으로 컴퓨터 언어 처음 배우면서 별 찍으라고 할 때보다는 덜 막막하다 ㅋㅋㅋㅋ

그때가 제일 막막했지... 아마도 ㅠㅠ ㅋㅋ