백준 15898 (피아의 아틀리에 ~신비한 대회의 연금술사) - java

 

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

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

 

유형 : 구현

 

접근 방식

• 삼성 코테가 좋아하는 유형의 문제이다. 로직을 분해하여 메소드 분리해보자
• 로직
  • 최대 10개인 재료에서 부어버릴 3개의 재료를 뽑아야 한다.
  • 각 재료를 가마에 추가한다. (이때 회전하여 넣을 수 있다)
  • 최댓값을 계산한다.
• 로직은 간단해보인다.
  • 10개의 재료 중에 3개를 선별 -> ???? 조합이다 !!!!
    • 물론 조합으로도 문제를 풀 수 있다. 하지만 위 문제의 경우 순열을 사용하는 것이 올바르다. 그 이유는 문제에 있다.
    • 격자의 색은 재료의 원소가 흰색인 경우 그대로, 아닌 경우 재료의 원소와 같은 색으로 칠해진다.
    • 색깔 조건에 의하면 해당 위치에 몇 번째 순서로 재료를 추가하는 지가 중요하다. 예를 들어 (R,G)일경우 해당 격자에는 G가 칠해지겠지만 (G,R)일 경우 해당 격자에는 R이 칠해지게 된다.
  • 즉 처음에 개수에서 3개를 추출할 때 순열로 구하면 칠해지는 순서까지 고려할 수 있다.
• 로직은 간단하지만 시간 초과...
  • 대략 시간 복잡도를 계산해보자
    • 10P3 * (3개의 격자를 전부 돌려보는 경우) * 칠하고 계산이다.
    • 격자를 돌려놓은 결과를 미리 저장하여 추가적인 연산을 줄이는 것이 중요하다.
    • 그리고 내가 이 문제를 풀 때 시간 초과가 발생하였는데 결과 격자를 매번 생성 하는 과정에서 발생하였다.
      • 결과를 추출한 경우 0으로 초기화하는 로직을 추가하여 이러한 과정을 없앴다.
      • 사실 그냥 java에게 관대하지 않은 문제인거 같다. (파이썬으로 푸시는 분들은 ... 이 말을 보고 화가 나시겠지만)
  • 재료를 칠하는 것은 시작 좌표 4개만 적용해보면 된다. (1,1) , (1,2) , (2,1) , (2,2)
    
    • 왜냐면 좌표를 나가는 경우는 적용하지 않는다고 하였기 때문에 4*4 배열이 전부 들어갈 수 있는 자리만 참고하면 된다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;

    static int[][][] board;

    static int[] ingredient;
    static boolean[] v;

    static int[][][][] pos;
    static int[][][][] color;

    static int[] sx = {1,1,2,2};
    static int[] sy = {1,2,1,2};

    static int re = 0;

    static int[] tmp;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());

        ingredient = new int[n+1];
        v = new boolean[n+1];

        pos = new int[n+1][5][5][5]; // 첫번째 재료, i, j, k(0 -> 90 -> 180 -> 270) 회전 (숫자)
        color = new int[n+1][5][5][5]; // 첫번째 재료, i, j, k(0 -> 90 -> 180 -> 270) 회전 (색깔)

        for(int k=1;k<=n;k++){

            for(int i = 1; i<=4 ;i ++){
                st = new StringTokenizer(bf.readLine(), " ");

                for(int j=1;j<=4;j++){
                    pos[k][i][j][1] = Integer.parseInt(st.nextToken());
                }
            }


            for(int i = 1; i<=4 ;i ++){
                st = new StringTokenizer(bf.readLine(), " ");

                for(int j=1;j<=4;j++){
                    char cur = st.nextToken().charAt(0);

                    if(cur == 'R'){
                        color[k][i][j][1] = 1;
                    }else if(cur == 'B'){
                        color[k][i][j][1] = 2;
                    }else if(cur == 'G'){
                        color[k][i][j][1] = 3;
                    }else if(cur == 'Y'){
                        color[k][i][j][1] = 4;
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            turn(i); // 미리 n개의 재료를 돌려놓은 결과를 저장해놓자 (시간 초과 방지)
        }


        peek(1); // n개 재료 중에 3개를 뽑고 진행
        System.out.println(re);

        bf.close();
    }

    static void peek(int num){

        if(num > 3){
            make();
            return;
        }
        // 순열
        for(int i= 1;i<=n;i++){
            if(!v[i]){
                v[i] = true;
                ingredient[num] = i;
                peek(num+1);
                v[i] = false;
            }
        }
    }

    static void make() {
        for(int f=1;f<=4;f++){
            for(int s=1;s<=4;s++){
                for(int t=1;t<=4;t++){
                    printAll(f,s,t); // 1,2,3번째 재료를 각각 몇번 돌린 결과로 수행할것인가
                }
            }
        }
    }

    static void printAll(int t1,int t2,int t3){

        board = new int[6][6][2];

        for(int pos1 = 0; pos1 < 4; pos1 ++){
            for(int pos2 = 0 ; pos2 < 4 ; pos2 ++){
                for(int pos3 = 0; pos3 < 4; pos3 ++){
                    print(pos1,ingredient[1], t1); // 1번째 재료 칠하기
                    print(pos2,ingredient[2], t2); // 2번째 재료 칠하기
                    print(pos3,ingredient[3], t3); // 3번째 재료 칠하기

                    result();
                }
            }
        }
    }

    static void result(){

        tmp = new int[5];

        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                tmp[board[i][j][1]] += board[i][j][0];
                board[i][j][0] = board[i][j][1] = 0;
            }
        }

        re = Math.max(re,(7*tmp[1] + 5*tmp[2] + 3*tmp[3] + 2*tmp[4]));
    }

    static void print(int cur,int num,int t){

        int px = 1;
        int py = 1;

        for(int i=sx[cur];i<=sx[cur] + 3;i++){
            for(int j = sy[cur];j <= sy[cur] + 3;j++){

                board[i][j][0] = sum(board[i][j][0],pos[num][px][py][t]);
                board[i][j][1] = color(board[i][j][1],color[num][px][py][t]);
                py += 1;
            }
            px += 1;
            py = 1;
        }
    }

    static void turn(int num){

        for(int k=2;k<=4;k++) {
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    pos[num][i][j][k] = pos[num][j][5 - i][k-1];
                    color[num][i][j][k] = color[num][j][5 - i][k-1];
                }
            }
        }

    }

    static int sum(int num,int tmp){
        if(num + tmp < 0)
            return 0;

        else if(num + tmp > 9)
            return 9;

        return num + tmp;
    }

    static int color(int num,int tmp){
        if(tmp == 0)
            return num;

        return tmp;
    }
}