[SW Expert] 1812. 수정이의 타일 자르기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yGVsKC0YDFAUx

SW Expert Academy

풀이

제약 사항

1 ≤ N ≤ 500

1 ≤ M ≤ 2^31 – 1

동작 순서

N = 2, M=5 일 때

Tiles에 입력받은 N값들을 저장한다.

rects 리스트에 사용할 타일을 add한다. 주어진 타일(m)은 5이기 때문에 처음에는 (m,m) 즉 (5,5) 타일 add한다.

(rects 리스트에 들어가는 것은 사각형의 W,H 이다. (w,h)를 나타낸다.)

이제 입력받은 N값들 하나씩 꺼내서 rects list 안에 있는 사용할 타일들을 비교한다.

만약 rects list 안에 있는 타일들을 사용한다면 다음과 같이 (1,4)와 (5,1)의 타일이 남게 된다.

사용하고 남은 타일들을 다시 rects list에 add한다.

 

만약 사용할 수 없다면 주어진 타일(m)을 사용하고 (사용할 때 result +1을 해준다.) 남은 타일을 list에 add한다.

---

코드

package swexpert.D5;

import java.util.*;

public class 수정이의타일자르기_SW1812 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList<Integer> tiles = new ArrayList<>();           //입력받은 n개의 타일들
            for (int i = 0; i < n; i++) {
                int v = sc.nextInt();
                tiles.add((int) Math.pow(2, v));
            }
            tiles.sort(Comparator.reverseOrder());

            System.out.println("#" + t + " " + getTiles(n, m, tiles));

        }
    }

    private static int getTiles(int n, int m, ArrayList<Integer> tiles) {
        int result = 1;
        ArrayList<Rect> rects = new ArrayList<>();
        rects.add(new Rect(m, m));

        for (int i = 0; i < n; i++) {
            int targetTile = tiles.get(i);
            boolean addTile = true;
            int size = rects.size();
            for (int j = 0; j < size; j++) {
                Rect tmp = rects.get(j);
                if (tmp.w - targetTile >= 0 && tmp.h - targetTile >= 0) {
                    //타일 사용할 수 있음
                    addTile = false;
                    if (tmp.h - targetTile > 0 && targetTile > 0)
                        rects.add(new Rect(targetTile, tmp.h - targetTile));
                    if (tmp.h > 0 && tmp.w - targetTile > 0)
                        rects.add(new Rect(tmp.w - targetTile, tmp.h));
                    rects.remove(j);
                    break;
                }
            }
            if (addTile) {
                result++;
                rects.add(new Rect(targetTile, m - targetTile));
                rects.add(new Rect(m - targetTile, m));

            }

        }
        return result;
    }

    static class Rect {
        int w, h;
        public Rect(int w, int h) {
            this.w = w;
            this.h = h;
        }

    }

}