2116번: 주사위 쌓기 (acmicpc.net)
알고리즘 시험 대비해서 백준에서 문제를 풀어보았다.
문제 자체가 특별히 어렵거나 하지 않았지만, 구현하면서 헷갈리는 부분이 있었다.
그래서 처음에 배열로 구현하려다가 주사위 클래스를 만들어서 풀었다.
일단 문제에서 첫 번째 주사위의 경우는 아무 방향으로 놓을수 있지만, 다음 주사위는 아래에 있는 주사위의 윗면과 놓는 주사위의 밑면의 숫자가 같아야한다.
즉 밑에 있는 주사위의 윗면을 체크해야한다.
그리고 그렇게 해서 전부 주사위를 쌓았을 때 얻을 수 있는 합의 최대를 구해야한다.
이 부분은 생각보다 쉽다.
밑면과 윗면은 고정되지만, 옆면은 회전시킬수 있기 때문이다.
예를 들어 밑면이 1 윗면이 6이라면 1과 6을 제외한 나머지(2,3,4,5) 중 최대값인 5를 더해주면 되는것이다.
결국 처음 시작하는 주사위를 선택 하는 경우의수 가 6개이고 나머지는 첫 주사위에 종속적이기 때문에, 경우의 수는 크게 6가지가 나올 수 있다.
나머지는 밑면과 윗면을 제외한 4면의 최대값을 누적시키기만 하면 된다.
따로 계산이 필요없는 이유는 회전시켜서 얻을 수 있는 옆면의 최대가 결국 4면의 최대값이고 각 최대값을 더한 것이 쌓인 주사위의 최대 합이 되기때문이다.
최종적으로 6가지 경우에서 각 누적된 값을 비교해서 가장 큰 값이 답이 될 것이다.
package com.algo.boj; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; class Dice{ int A,B,C,D,E,F,top,bottom; List<Integer> four; public Dice(){} public Dice(int[] input){ four = new ArrayList<>(); A = input[1]; B = input[2]; C = input[3]; D = input[4]; E = input[5]; F = input[6]; } public List<Integer> getfour() { four.clear(); four.add(A); four.add(B); four.add(C); four.add(D); four.add(E); four.add(F); four.remove(Integer.valueOf(top)); four.remove(Integer.valueOf(bottom)); return four; } public int getMaxfour() { return Collections.max(getfour()); } public void setBottom(int i){ switch (i) { case 1 : bottom = A; top = F; break; case 2 : bottom = B; top = D; break; case 3 : bottom = C; top = E; break; case 4 : bottom = D; top = B; break; case 5 : bottom = E; top = C; break; case 6 : bottom = F; top = A; break; } } } public class BOJ2116Dice { private static List<Dice> list; private static int max; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N =Integer.parseInt(br.readLine()); int map[][] = new int[N][6+1]; list = new ArrayList<>(); for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine(), " "); for (int j = 1; j <= 6; j++) { map[i][j] = Integer.parseInt(st.nextToken()); } list.add(new Dice(map[i])); }//input 입력 for max=0; for (int i = 1; i <= 6; i++) { //a,b,c,d,e,f 차례대로 바닥에 두기 Dice base = list.get(0); base.setBottom(i); recursiveDice(1, base.top, base.getMaxfour()); } System.out.println(max); }//main private static void recursiveDice(int cnt, int top, int sum) { if(cnt>= list.size()) { max = Math.max(max, sum); return; } Dice dice = list.get(cnt); for (int i = 1; i <= 6; i++) { //a,b,c,d,e,f 차례대로 바닥에 두기 dice.setBottom(i); if(dice.bottom!=top)continue; recursiveDice(cnt+1, dice.top, sum+dice.getMaxfour()); } } }
나는 여기서 입력을 Dice객체를 생성해서 할당하였고, 입력과 동시에 ABCDEF라는 전개도 개념으로 값을 할당하였다.
switch문을 이용해서 주사위의 밑면과 윗면을 설정하도록 하였다.
그리고 getfour()라는 메소드는 top 과 bottom을 제어한 리스트를 반환한다.
여기서 getMaxfour는 getfour중에서 가장 큰 값을 반환한다.