[BaekJoon/백준] 1932번 | 복습 1회 완료

이전의 1149번과 매우 유사한 문제였다.

#include <stdio.h>
#define MAX(a,b) (a<=b)?b:a

int m[500][500];
int y[500][500];

int main() {

    int N;
    int max=0;
    scanf("%d", &N);
    int left=1, right=1;
    
    scanf("%d", &m[0][0]);
    
    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i + 1; j++) {
            scanf("%d", &m[i][j]);
        }
    }
    
    y[0][0] = m[0][0];
    
    for(int i = 1; i < N; i++) {
        for(int j = 0; j < i + 1; j++) {
            left = right = 1;
            if(j <= 0)
                left = 0;
            if(j >= i)
                right = 0;
            
            if(left != 0)
                left = y[i - 1][j - 1];
            if(right != 0)
                right = y[i - 1][j];
            y[i][j] = (MAX(left, right)) + m[i][j];
            
            if(max < y[i][j])
                max = y[i][j];
        }
    }
    printf("%d", max);
}

이전 R G B 문제와 마찬가지로, i 번째 행의 각 j 인덱스 값들에, 그 전까지의 결과 중 최댓값을 더해 최댓값 가능성을 쌓아올려나아가고

마지막 N - 1 행에서 각 j열에 생성되어있는 최댓값 후보들 중 최댓값을 뽑아낸다.

포문에서 그 자리에서의 i 행 j 번째까지의 덧셈이, 올라오는 과정에서의 최댓값이 되기 위한 빌드를 짜 만들어 나가게 하는 것임.

ex ) N = 5라고 할 때

각 해당 자리(마지막 행 0~4열)에서의 5번째 덧셈이 해당 자리까지 오는 모든 경로의 덧셈 중 최댓값이 되기 위해선, 우선 해당 자리까지 오는 데의 4번째 까지의 덧셈이 최댓값인 상태여야하고, 3번째 까지의 덧셈이 최댓값인 상태여야 하고 ....

그리고 나서 모든 자리(마지막 행 0~4열 모두)에서의 5번째 덧셈을 마친 뒤(여기까지 오면, 각 자리까지 오는 데 최댓값이 된 경우들로만 구성되어 있음), 그 중 최댓값을 구하면 전체 경로에서의 최댓값을 얻게 된다. 그리고 0~4열 중 어느 경로가 마지막이여야 그런 결과가 나오는지도 알 수 있는 것.

 

 

 

그리고 반복문을 이용한 방식 말고, 재귀 형식으로도 구현해보고싶었다. (아래 코드는 시간 초과)

#include <stdio.h>
#define MAX(a,b) ((a<b)?b:a)
int arr[500][500];
int N;
int max = 0;

void list(int i, int j, int count, int result) {
    
    if(count >= N - 1) {
        result += arr[i][j];
        if(result > max)
            max = result;
        return;
    }

    list(i + 1, j, count + 1, (arr[i][j] + result));
    list(i + 1, j + 1, count + 1, (arr[i][j] + result));
}

int main() {
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < i + 1; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
        
    list(0, 0, 0, 0);
    
    printf("%d", max);

}

(여기서 result 를 일종의 check 배열형식으로 사용했다고 보면 되는데, check 배열이나 위의 result나 이전 뽑은 경우의 값들을 참고하고있으므로 저번 1149번 글에서 궁금해했듯이, 이것도 메모이제이션의 한 방향이라고 볼 수 있을지 확실히는 모르겠다..)

 

[잠깐, 1149번에 대해]----------------------

1. 순열/조합 코드의 check 배열이 메모이제이션이다 또는 아니다가 확실치 않다..

함수 1에서 함수 2로 간 뒤 함수 2에서 함수 1의 결과값을 다시 참조하는 대신에 메모이제이션을 사용하는 방면으로 봤을 때 이는 메모이제이션이라고 볼 수도 있다는 가능성을 갖고 있다..

2. 그리고 for문으로 구성했던 정답코드는 기본적으로 동작 내에서 [i][1], [i][2]/ [i][2][3] 등 이런식으로 중복되는 경우가 있으므로 이미 동적프로그래밍 기반 메모이제이션이라고 볼 수 있긴 한데, 그 외에도 바로 위에서 check 배열과 같은(이전 뽑은 경우의 값들을 참고) 흐름을 가지고 있어서 1번도 메모이제이션의 한 측면이 아닐까 라는 생각이 쫌 더 듦..

------------------------------------------

 

어쨌든 다시 돌아와서, 위 코드를 보면 알 수 있듯이

그냥 순열/조합 코드를 짤 때 처럼, 대각선으로 뽑는 모든 경우의 수를 뽑아나가면서 다 뽑을 때 최댓값을 비교하는 방식으로 구현했는데,

시간초과가 떴다.

 

 

이를 통해 알게 된 점은,

 

최댓값 / 최솟값을 뽑는 경우에는 

재귀를 이용한 순열과 조합 같은 Top - down 방식을 그대로 이용 (모든 뽑는 경우의 수를 찾아냄)하면 시간초과가 뜨는 풀이라는 것을 느꼈다. 다른 분의 재귀 Top - down 방식(www.acmicpc.net/board/view/36600)을 보니, 반복문을 이용한 Bottom - up 방식처럼 여전히 최댓값을 기반으로 계산해나가는 것을 알 수 있었다.

그리고 dp_triangle[n][c] = max(top_down(n - 1, c - 1), top_down(n - 1, c)) + triangle[n][c]; 이런 구문이 있어서 명확히 메모이제이션을 사용하고 있다는 것도 알 수 있었다.(이런 부분문제가 중복되는 경우(함수의 결과가 하나고, 똑같은 인자로 함수를 재호출하여 다시 값을 얻어내는 경우)는 명확히 메모이제이션이라는 걸 알겠는데ㅜㅜㅜ 메모이제이션이라고 보는건지 헷갈리는 것들이 꽤 있다ㅜ 차차 알아가자!)

 

 

참고

www.acmicpc.net/board/view/41258

글 읽기 - 동적계획법의 풀이에 대해서

 

 

---

2021.02.23 복습

다시풀어보았다. 이전보다 훨씬 간결하게 풀었다 !!

#include <stdio.h>
#define MAX(a,b) ((a>=b)?a:b)

int M; // 최댓값
int N;
int arr[501][501]; // 행-열을 하나 더 둬서 -1번째 인덱스에 오류가 없도록함. (0,0) 이 아닌 (1,1) 부터 시작.

int main() {
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= i; j++) {
            scanf("%d", &arr[i][j]);
            arr[i][j] += MAX(arr[i - 1][j - 1], arr[i - 1][j]);
        }
    }
    
    // 마지막 행의 각 열 중에서 최댓값을 찾기
    M = arr[N][1];
    for(int i = 2; i <= N; i++) {
        if(M < arr[N][i])
            M = arr[N][i];
    }
    
    printf("%d", M);

}

참고로 이문제나, 1149번이나

이후 계단문제, 와인잔문제와는 같은 동적계획법 풀이고 거의 비슷한 흐름이지만 유형이 쪼오끔 달라서 과정이 쫌 다르다는 걸 풀다보면 알 수 있다.