SW Expert - 1812 수정이의 타일 자르기(Java)

그리디 문제입니다.

 

이 문제를 풀기 위해서는 한 가지 아이디어가 필요합니다.

필요 타일의 크기 중 가장 큰 것 먼저 자른다.

즉, 내림차순으로 문제를 해결하면 됩니다.

 

M*M에서 N*N 만큼 타일을 자르면 아래의 그림과 같이 구역이 나눠집니다.

즉, M*(M-N) 과 (M-N)*N이 남습니다.

 

문제 전체 접근 순서는 다음과 같습니다.

1. 필요 타일의 크기(N*N)들을 구해서 리스트에 저장한다.
2. 크기를 내림차순으로 정렬한다.
3. 내림차순으로 정렬된 요소를 하나씩 확인하면서 타일을 자른다.
   1. 타일을 자를 수 있으면 자르고 남은 두 개의 타일을 저장한다.
   2. 타일을 자를 수 없다면 하나의 새로운 타일을 추가하고 타일을 자른다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz;

        int t = Integer.parseInt(br.readLine());

        for (int testCase = 1; testCase <= t; testCase++) {
            int answer = 0;
            stz = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(stz.nextToken());
            int m = Integer.parseInt(stz.nextToken());

            // 1. 필요 타일의 크기(N*N)들을 구해서 리스트에 저장한다.
            stz = new StringTokenizer(br.readLine());
            List<Integer> needTilesSizes = new ArrayList<>();
            for(int i=0; i<n; i++){
                int size = Integer.parseInt(stz.nextToken());
                needTilesSizes.add((int) Math.pow(2, size));
            }

            // 2. 크기를 내림차순으로 정렬한다.
            needTilesSizes.sort(Collections.reverseOrder());

            answer = calNeedTiles(m, needTilesSizes);

            System.out.printf("#%d %d" + System.lineSeparator(), testCase, answer);
        }

        br.close();
    }

    private static int calNeedTiles(int m, List<Integer> needTilesSizes) {
        int count = 1;
        List<int[]> rects = new ArrayList<>();
        rects.add(new int[]{m, m});

        // 3. 내림차순으로 정렬된 요소를 하나씩 확인하면서 타일을 자른다.
        for (int needTilesSize : needTilesSizes) {
            boolean isNeedNewTile = true;

            for(int i=0; i<rects.size(); i++){
                int w = rects.get(i)[0];
                int h = rects.get(i)[1];

                // 3.1 타일을 자를 수 있으면 자르고 남은 두 개의 타일을 저장한다.
                if(w >= needTilesSize && h >= needTilesSize){
                    rects.add(new int[]{w, h-needTilesSize});
                    rects.add(new int[]{w-needTilesSize, needTilesSize});
                    rects.remove(i);

                    isNeedNewTile = false;
                    break;
                }
            }

            // 3.2 타일을 자를 수 없다면 하나의 새로운 타일을 추가하고 타일을 자른다.
            if(isNeedNewTile){
                count++;
                rects.add(new int[]{m, m-needTilesSize});
                rects.add(new int[]{m-needTilesSize, needTilesSize});
            }
        }

        return count;
    }
}