[SW Expert Academy] 4335. 무인도 탈출

4335. [연습문제] 무인도 탈출

SW Expert Academy의 문제들은 저작권 때문에 무단 복제가 금지되어있기 때문에 링크로 대체하겠습니다.

클릭시 이동합니다!

어떻게 풀까?

우선 직육면체의 특징에 대해서 살펴봅시다!

직육면체는 말 그대로 6개의 면을 가지고 있습니다.

하지만, 생각해보면 그 특징은 가로, 세로, 높이의 세 가지 길이로 이루어져있죠!

즉, {가로, 세로}, {세로, 높이}, {높이, 가로}의 세 가지 방향으로 놓을 수 있다는 것을 알 수 있습니다!!

또한, 블록의 특성상 메모이제이션을 쓰면 굉장히 적절할 것 같다는 생각을 해볼 수 있습니다.

20개의 블록이니까 비트로 나타내서 비트를 이용한 메모이제이션을 사용하면 될 것입니다!

어떤 비트가 주어지면, 값이 0 으로 세팅되어있는 블록들을 이용해서 만들수 있는 가장 높은 높이를 메모리에 저장합시다!

예를 들면, 00011 이라면, 현재 사용한 블록은 1번과 1번 비트가되기 때문에, 3,4,5번 블록을 사용해서 만들 수 있는 가장 높은 높이가 해당 메모리에 저장될 것입니다.

하지만, 생각해보면 해당 문제는 사용하지 않은 블록만으로 해결할 수 없다는 것을 쉽게 알 수 있습니다!

바로, 윗면의 길이가 다를 경우 채워 넣을 수 있는 블록이 달라지기 때문이죠!

따라서, 윗면의 상태를 나타내줄만한 처리가 필요합니다.

우선, 하나의 도형을 봅시다!

직육면체는 위, 아래, 옆 총 3방향에서 볼 수 있습니다!

윗 면의 상태도 따라서 3개가 나올 수 있습니다.

추가적으로, 맨 위에 있는 직육면체의 종류에 따라서 또 다시 윗면의 상태가 달라집니다!

(여담이지만, 3D로 뭔가 올리니까 재밌네요...)

따라서, 메모이제이션에는 이렇게 3가지의 정보가 필요하겠군요!

1. 선택되는 블록이 어떤것인가? -> 비트를 이용해 표현

2. 어떤 블록이 맨 위에 있는가? -> 블록 번호로 표현

3. 윗면인가 아랫면인가 옆면인가? -> mode라는 변수를 통해 표현

이렇게 3 차원 배열을 이용합시다!

이렇게 하면, 어떤 블록을 맨 위에 놓을지, 윗 방향인지, 아랫 방향인지, 옆 방향인지도 다 알 수 있습니다.

mode에 따라서 윗면의 2 길이가 정해집니다. 따라서, 쌓아진 블록의 높이는 선택되지 않은 나머지 길이 라는 것을 알 수 있죠.

즉, mode에서 윗 면의 길이로 선택되지 않은 길이를 쌓인 블록의 높이로 더해주면 되는 것 입니다!

이제 재귀함수를 통해서, 맨 윗면에 들어가는 면을 정할 수 있고, 만들어지는 총 블럭의 높이도 구할 수 있습니다!

따라서, 메모리에 n개의 블록을 정하고, 윗 면이 S일때 만들 수 있는 최고의 높이를 저장할 수 있습니다.

이 메모이제이션을 통해 만들 수 있는 최대의 높이를 구합시다!

코드

//https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWL6HGz6Ai4DFAUY
//무인도 탈출
#pragma once
#include<stdio.h>
 
int cache[21][1 << 20][3];
int infos[21][3], n;
 
void swap(int &i1, int &i2) {
    int temp = i1;
    i1 = i2;
    i2 = temp;
}
 
int max(int i1, int i2) {
    return i1 < i2 ? i2 : i1;
}
 
int getLength(int now, int mode, int row, int col, int visit) {
    int &ret = cache[now][visit][mode];
    if (ret) return ret;
    
    for (int i = 1; i <= n; i++) {
        if (visit & (1 << (i-1))) continue;
        int nv = visit | (1 << (i-1));
        if (row >= infos[i][0] && col >= infos[i][1]) {
            ret = max(ret, infos[i][2] + getLength(i, 0, infos[i][0], infos[i][1], nv));
        }
        if (row >= infos[i][0] && col >= infos[i][2]) {
            ret = max(ret, infos[i][1] + getLength(i, 1, infos[i][0], infos[i][2], nv));
        }
 
        if (row >= infos[i][1] && col >= infos[i][2]) {
            ret = max(ret, infos[i][0] + getLength(i, 2, infos[i][1], infos[i][2], nv));
        }
    }
    return ret;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
    infos[0][2] = infos[0][0] = infos[0][1] = 0x3f3f3f3f;
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d\n", &n);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 1 << (n); j++) {
                for (int k = 0; k < 3; k++) cache[i][j][k] = 0;
            }
        }
 
        for (int i = 1; i <= n; i++) {
            scanf("%d %d %d\n", &infos[i][0], &infos[i][1], &infos[i][2]);
            if (infos[i][0] > infos[i][1]) swap(infos[i][0], infos[i][1]);
            if (infos[i][1] > infos[i][2]) swap(infos[i][1], infos[i][2]);
            if (infos[i][0] > infos[i][1]) swap(infos[i][0], infos[i][1]);
        }
 
        printf("#%d %d\n", tc, getLength(0, 0, 0x3f3f3f3f, 0x3f3f3f3f, 0));
    }
    return 0;
}
 

여담

시간 복잡도는 어떻게 될까요!?

부분 집합의 개수는 이고, 함수에서 n번을 반복하기 때문에 총!

의 시간복잡도가 나옵니다.

굉장히 어마어마한 시간복잡도군요...