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

메모이제이션을 사용하는 동적계획법을 알고 있느냐에 관한 개념적인 문제였다.

 

문제에서는 부분문제가 중복되는 상황에서 메모이제이션을 사용하지 않고, 재귀를 반복 호출하여 비효율적인 실행을 진행하고 있다.

따라서 메모이제이션을 적용해주면 된다.

// 문제에서는 메모이제이션을 사용하지 않는다. 따라서 메모이제이션을 사용하여 효율을 높인다.
#include <stdio.h>
#include <string.h>
int arr[101][101][101]; // 범위는 -50 ~ 50 이므로, +50시켜서 0 ~ 100까지로 만든다.

int memo(int a, int b, int c) {
    if(arr[a][b][c] != 0)
        return arr[a][b][c];
    
    if (a <= 50 || b <= 50 || c <= 50) // 범위가 변경되었으니, 기존 0에서 + 50
        return 1;

    else if(a > 70 || b > 70 || c > 70) // 범위가 변경되었으니, 기존 20에서 + 50
        return arr[a][b][c] = memo(70, 70, 70); // 범위가 변경되었으니, 기존 20에서 + 50

    else if (a < b && b < c)
        return arr[a][b][c] = memo(a, b, c-1) + memo(a, b-1, c-1) - memo(a, b-1, c);
        
    else
        return arr[a][b][c] = memo(a-1, b, c) + memo(a-1, b-1, c) + memo(a-1, b, c-1) - memo(a-1, b-1, c-1);

}

int main() {
    
    int a, b, c;
    
    while(1) {
        scanf("%d %d %d", &a, &b, &c);
        
        if(a == -1 && b == -1 && c == -1)
            break;
        
        printf("w(%d, %d, %d) = %d\n", a, b, c, memo(a + 50, b + 50, c + 50)); // 범위가 변경되었으니 + 50 해서 전달.
    }
}

---

2021.02.23 복습

다시풀어보았다. 

 

풀면서 느낀건데, 타뷸레이션은 미리 문제의 범위내에서 모두 만들어낸다는 점과 달리(꼭 이럴필요는없겠지만ㅎㅎ 보통)

메모이제이션은 그때그때 필요한만큼 만든다는 점이 좀 다른 것 같다는 생각을 했다. -> 한번이 아닌 여러 입력을 받을 때, 각각의 값 도출을 위한 경우에서 둘의 차이를 느낄 수 있었다.

#include <stdio.h>

int key[101][101][101];


int w(int x, int y, int z) {
    
    if(key[x][y][z])
        return key[x][y][z];
    
    if(x <= 50 || y <= 50 || z <= 50)
        return 1;
    
    else if(x > 70 || y > 70 || z > 70)
        return key[x][y][z] = w(70, 70, 70);

    else if(x < y && y < z)
        return key[x][y][z] = w(x, y, z-1) + w(x, y-1, z-1) - w(x, y-1, z);

    else
        return key[x][y][z] = w(x-1, y, z) + w(x-1, y-1, z) + w(x-1, y, z-1) - w(x-1, y-1, z-1);

}

int main() {
    
    int a, b, c;
    
    while(1) {
        scanf("%d %d %d", &a, &b, &c);
        
        if(a == -1 && b == -1 && c == -1)
            break;
        
        printf("w(%d, %d, %d) = %d\n", a, b, c ,w(a+50, b+50, c+50));
    }
}