[BOJ] 15898 : 피아의 아틀리에 ~신비한 대회의 연금술사~ [G1]

 

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

15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~

 

 

 

[문제]

"피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타야만 피아가 먹고 살 수 있기 때문이다. 스토리는 매우 길지만 여백이 없어 생략하기로 하고, 여러분은 이 게임의 대회 기능을 확인해달라는 요청을 받았다. 여러분이 확인해야 하는 대회는 다음과 같다.

여러분은 5×5 격자 모양 가마에 서로 다른 재료 3개를 순서대로 넣어 최고 품질의 폭탄을 만들어야 한다. 재료는 대회에서 준비해주며, 넣을 수 있는 재료의 후보는 10개 이하이다. 주어진 재료 중 3개를 고른 뒤, 순서를 정해 가마에 잘 넣어야 한다.

가마의 각 칸에는 품질을 나타내는 숫자와 원소를 나타내는 색이 칠해져 있다. 초기에는 모든 칸의 품질은 0, 원소는 흰색이다. 재료는 4×4 모양으로 생겼으며, 재료의 i행 j열에는 2가지 정보가 있다.

1. 효능: 가마 한 칸의 품질을 바꾸는 -9 이상 9 이하의 정수 xi,j
2. 원소: 가마 한 칸의 원소를 바꿀 수 있는 색 ci,j (빨강 'R', 파랑 'B', 초록 'G', 노랑 'Y', 흰색 'W' 중 하나이다)

재료를 가마에 넣을 때는 5×5 격자를 벗어날 수 없다. 회전은 가능하나, 격자에 맞지 않게 기울여 넣을 수는 없다. 재료를 가마에 넣을 때, 가마의 상태는 다음과 같이 바뀐다.

1. 재료가 위치하지 않는 가마의 격자칸은 아무런 변화가 생기지 않는다.
2. 재료가 위치한 가마의 격자칸에 있는 품질과 원소값은 바뀔 수 있다.
   • 격자의 품질은 재료의 효능이 더해진다. 더한 뒤의 값이 음수인 경우 0으로, 9 초과인 경우 9로 바뀐다.
   • 격자의 색은 재료의 원소가 흰색인 경우 그대로, 아닌 경우 재료의 원소와 같은 색으로 칠해진다.

재료 3개를 모두 넣어야만 폭탄이 만들어지며, 폭탄의 품질은 다음과 같이 계산된다. 가마의 최종 상태에서 빨강, 파랑, 초록, 노랑으로 칠해진 부분의 품질 합을 각각 R, B, G, Y라고 했을 때,

(폭탄의 품질) = 7R + 5B + 3G + 2Y

폭탄을 만들기 위한 재료의 후보가 주어졌을 때, 재료를 적절히 선택하고 배치하여 만들 수 있는 폭탄의 최대 품질을 구하자.

 

[입력]

첫 번째 줄에 재료의 개수를 나타내는 자연수 n이 주어진다. (3 ≤ n ≤ 10)

두 번째 줄부터 n개의 재료 정보가 순서대로 주어진다. 각 재료의 정보는 다음과 같다. 먼저 4개의 줄에 효능을 나타내는 수 4개가 공백을 사이에 두고 주어진다. 다음 4개의 줄에 원소를 나타내는 글자 4개가 공백을 사이에 두고 주어진다. 이 글자는 R, B, G, Y, W 중 하나임이 보장된다.

[출력]

첫 번째 줄에 품질의 최댓값을 출력한다.

 

[예제 입력 1]

4
6 3 3 -9
-6 8 -6 8
9 5 1 -1
-8 2 -3 -1
R B G Y
Y B R R
W R R R
G R W B
-6 -2 -4 -3
1 -3 0 9
8 -7 2 0
0 3 -5 7
W B R Y
Y W R B
W B G G
Y G B R
8 7 2 1
-9 8 8 -9
-1 -4 8 6
-7 8 -3 8
Y W W G
Y B R B
Y W R R
R Y W Y
4 -5 8 3
2 3 1 3
-5 0 1 -3
4 3 3 -6
W Y G W
G G R W
G Y G R
R R G Y

[예제 출력 1]

634

 

 

[내 풀이]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/*
    문제 : [G1] 피아의 아틀리에 ~신비한 대회의 연금술사~ - 15898번
    제출 : 2024년 4월 6일
    결과 : 통과
    성능 요약 :
        최적화 전(배열 복사O) : 메모리 301032KB, 시간 2880ms
        최적화 후(배열 복사X) : 메모리 295620KB, 시간 2164ms
    아이디어 : 구현 + 시뮬레이션

*/

public class Main_15898_피아의아틀리에신비한대회의연금술사 {
    static int n;
    static int[][][][] effect; // (row, col, n번째 재료, 회전)
    static char[][][][] color;
    static List<Integer> itemPer = new ArrayList<>();
    static boolean[] isVisited;
    static List<Integer> rotatePer = new ArrayList<>();
    static List<Integer> putPer = new ArrayList<>();
    static Map<Integer, int[]> map = new HashMap<>();
    static int ans;

    // 뽑은 아이템, 회전 수, 넣는 위치를 뽑은 뒤 폭탄 품질 구하기
    static void calculate() {

        // 초기 배열
        int[][] effectGama = new int[5][5];
        char[][] colorGama = new char[5][5];

        // item : {0, 1, 2} n개의 아이템중에 1,2,3번쨰 아이템
        // rotate : {1, 2, 0} (0 : 0도, 1 : 90도, 2 : 180도, 3: 270도)
        // put : {0, 1, 1} (0 : (0,0), 1 : (0, 1), 2 : (1,0), 3: (1,1))
        // 첫번째 아이템 180도 회전해서 (0, 0)에 위치

        // 각 배열에 해당하는 동작 수행
        for (int i = 0; i < 3; i++) {
            int itemIdx = itemPer.get(i);
            int rotateIdx = rotatePer.get(i);
            int putIdx = putPer.get(i);

            int[] put = map.get(putIdx);
            int x = put[0];
            int y = put[1];

            for (int a = 0; a < 4; a++) {
                for (int b = 0; b < 4; b++) {
                    // 품질
                    effectGama[a+x][b+y] += effect[a][b][itemIdx][rotateIdx];
                    if (effectGama[a+x][b+y] < 0) effectGama[a+x][b+y] = 0;
                    else if (effectGama[a+x][b+y] > 9) effectGama[a+x][b+y] = 9;

                    // 색상 (흰색이 아닐때만 색칠)
                    if (color[a][b][itemIdx][rotateIdx] != 'W') colorGama[a+x][b+y] = color[a][b][itemIdx][rotateIdx];
                }
            }

        }

        // 완성된 가마에 대해 품질 구하기
        int count = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (colorGama[i][j] == 'R') count += (7 * effectGama[i][j]);
                else if (colorGama[i][j] == 'B') count += (5 * effectGama[i][j]);
                else if (colorGama[i][j] == 'G') count += (3 * effectGama[i][j]);
                else if (colorGama[i][j] == 'Y') count += (2 * effectGama[i][j]);
            }
        }

        // 최댓값 계산
        ans = Math.max(ans, count);
    }

    static void putPermutation(int depth) {
        if (depth == 3) { // 순열 뽑음
            calculate();
            return;
        }

        // 넣는 위치 4곳 중 하나 뽑기
        for (int i = 0; i < 4; i++) {
            putPer.add(i);
            putPermutation(depth + 1);
            putPer.remove(putPer.size() - 1);
        }
    }

    static void rotatePermutation(int depth) {
        if (depth == 3) { // 순열 뽑음
            // 가마에 넣는 순열
            putPermutation(0);
            return;
        }

        // 4방향 중 하나 뽑기
        for (int i = 0; i < 4; i++) {
            rotatePer.add(i);
            rotatePermutation(depth + 1);
            rotatePer.remove(rotatePer.size() - 1);
        }
    }

    static void itemPermutation(int depth) {
        if (depth == 3) { // 재료 순열 뽑음 (단, 중복 X)
            // 회전 순열
            rotatePermutation(0);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                itemPer.add(i);
                itemPermutation(depth + 1);
                isVisited[i] = false;
                itemPer.remove(itemPer.size() - 1);
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());

        // (r, c, n) : row, col, n번째, 회전
        effect = new int[4][4][n][4];
        color = new char[4][4][n][4];
        for (int c = 0; c < n; c++) {
            // 효능
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++) {
                    effect[i][j][c][0] = Integer.parseInt(st.nextToken());
                }
            }

            // 원소
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++) {
                    color[i][j][c][0] = st.nextToken().charAt(0);
                }
            }
        }

        // 배열 돌리기
        for (int c = 0; c < n; c++) { // 모든 재료에 대해
            for (int rotate = 1; rotate < 4; rotate++) { // 90도, 180도, 270도 회전
                // 효능
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        effect[i][j][c][rotate] = effect[4-(1+j)][i][c][rotate-1];
                    }
                }

                // 원소
                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 4; j++) {
                        color[i][j][c][rotate] = color[4-(1+j)][i][c][rotate-1];
                    }
                }
            }
        }

        // 재료 놓는 위치
        map.put(0, new int[]{0, 0});
        map.put(1, new int[]{0, 1});
        map.put(2, new int[]{1, 0});
        map.put(3, new int[]{1, 1});

        isVisited = new boolean[n];
        // 재료 순열
        itemPermutation(0);

        System.out.println(ans);
    }

}

 

 

[회고]

처음 시간 복잡도를 구했을 때,

 

n개 중에 재료 3개를 뽑기 nP3
뽑은 재료 -> 회전하게되면 회전 방향 4개 (4 * 4 * 4)
뽑고, 회전한 재료 -> 가마에 놓기 (0,0), (0,1), (1,0), (1,1) (4 * 4 * 4)

✔ O(n) : nP3 * (4^3) * (4^3) = 2,949,120 (최악, n=10)

 

이고 시간제한이 3초이기때문에 brute-force를 해도 바로 풀릴 줄 알았다.

하지만 회전하는 배열을 구할 때, 각 케이스마다 회전하는배열을 구하고 복사하게되면

 nP3 * (4^3) * (4^3) * (원본 배열 복사 시간) * (배열 회전 시간)이 되어

제한시간을 넘어가 버린다.

 

따라서 

 

effect : 효능, color : 색깔 담은 배열

 

 

4차원 배열을 선언해 각 회전했을 때의 배열을 미리 저장해두고 사용해 시간복잡도 문제를 해결.