직육면체 자르기

Software Expert Academy [24696] 직육면체 자르기

풀이

직육면체에 짝수 길이가 있다면 자를 수 있는 상태로 간주한다. 자른 후에도 추가적으로 자를 수 있는 상태라면 잘린 양쪽 직육면체 모두를 다시 목록에 추가한다. 자를 수 없는 상태를 맞이했을때 진 것으로 간주한다

소스코드

import java.util.*;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            int C = sc.nextInt();
 
            int[] cube = {A, B, C};
            Queue<int[]> cubeList = new ArrayDeque<>();
            cubeList.add(cube);
 
            int result = 2;
            while (!cubeList.isEmpty()) {
                boolean isCut = canCutCube(cubeList);
 
                if (isCut) {
                    if (result == 1) {
                        result = 2;
                    } else {
                        result = 1;
                    }
                }
            }
 
            System.out.println(result);
        }
    }
 
    private static boolean canCutCube(Queue<int[]> cubeList) {
        boolean isCut = false;
 
        int[] cube = cubeList.poll();
 
        for (int i = 0; i < cube.length; i++) {
            int cut = cube[i] % 2;
            if (cut == 0) {
                if (isCut) {
                    // 잘린 후에도 더 자를 수 있는 경우 잘린 두 직육면체를 리스트에 추가
                    cubeList.add(cube.clone());
                    cubeList.add(cube.clone());
 
                    break;
                } else {
                    isCut = true;
                    cube[i] = cube[i] / 2;
                }
            }
        }
 
        return isCut;
    }
}