[백준][JAVA] 18230 - 2XN 예쁜 타일링 - 그리디

📌 문제

백준 | 2XN 예쁜 타일링 | level1 | 그리디

https://www.acmicpc.net/problem/18230

 

📌 문제 탐색하기

• 화장실 바닥은 2 X N 크기의 격자로 표현된다.
  • 2X1 A개, 2X2 B개 존재
  • 화장실 바닥의 예쁨 = 각 타일들의 예쁨의 합
  • 예쁨이 최대로 타일링을 하고 싶음
• 출력값 = 예쁨의 최댓값은 얼마일까 ?

 

📌 알고리즘

• 2X1 타일과 2X2 타일들을 어떻게 배치하느냐에 따라 2XN 타일을 만들 수 있음
• 이때, 2X1은 돌려서 1 X 2도 될 수 있음
• 그러므로 총 가능한 경우의 수가 2X1, 2X2, 1X2 3가지임
• 그러므로 n을 분리해서 나올 수 있는 경우를 먼저 찾고, 그 값에 맞춰서 타일들 중 예쁨의 크기가 큰 것들 부터 합산해주기 시작한다.
  • 이때, 각 단계에서 ‘최적해’를 구하려 해야하며, 이를 위해 ‘가장 큰 예쁨 타일 부터 선택’ 해 나아가야 한다 (그리디 알고리즘)

 

📌 작은 단계로 나눠서 고민

첫번째부터 가장 큰 예븜 타일을 고르기 위한 고민

• N이 홀수인 경우
  • 2X1 타일은 무조건 1개 (1X2로 돌릴것) + 2X2 타일 N/2개
  ⇒ 그러므로 2X1개 중에서 가장 큰 값 타일 고르기
• N이 짝수인 경우
  • 2X2 타일 N/2 또는 2X1 타일 2개를 묶어서 N/2개
  ⇒ 2X1 타일 들 중 가장 큰 값 2개 OR 2X2 타일 들 중 가장 큰 값

---

• 가장 큰 값부터 사용하기 위해 Arrays.sort로 배열 정렬하기 ⇒ O(AlogA) + O(BlogB)
• N이 홀수라면, 2X1 중 가장 큰 값을 하나 사용하고, 정답에 합산하기
• 그 뒤에 N 이 짝수가 되므로 N/2개의 2X2 타일을 만들어야함
  • 2X1 타일 2개이상 → 기록
  • 2X2 타일 1개이상 → 기록
  ⇒ O(N)

결과적으로 O(AlogA) + O(BlogB) + O(N) = O(NlogN) ⇒ 시간제한 2초 안에 충분히 가능

 

 

 

📌 코드 설계하기

1. N,A,B 입력받기
2. A,B 중에서도 크기가 큰 것들 위주로 진행하기

 

 

📌 시도 회차 수정 사항 

1회차

• Arrays에 담아두고 계속 copyOfRange로 문제를 풀다보니,, 런타임에러가 발생했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


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

        int answer = 0;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        Integer[] aPoint = new Integer[a];
        Integer[] bPoint = new Integer[b];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < a; i++) {
            aPoint[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(aPoint, Collections.reverseOrder());


        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < b; i++) {
            bPoint[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(bPoint, Collections.reverseOrder());


        if (n % 2 == 1) {
            answer += aPoint[0];
            aPoint = Arrays.copyOfRange(aPoint, 1, a);
        }

        for (int i = 0; i < n / 2; i++) {
            int tmp = 0;
            if (aPoint.length >= 2) {
                tmp = Math.max(tmp, aPoint[0] + aPoint[1]);
            }
            if (bPoint.length >= 1) {
                tmp = Math.max(tmp, bPoint[0]);
            }

            if (tmp == bPoint[0]) {
                bPoint = Arrays.copyOfRange(bPoint, 1, b);
            } else {
                aPoint = Arrays.copyOfRange(aPoint, 2, a);
            }

            answer += tmp;
        }
        System.out.println(answer);
    }
}

2회차

• Array에 담지 말고. Queue에 담음으로써 pop이 용이하도록 구현해보자.
  • 또한, Arrays.sort를 하지 않도록 애초에 PriorityQueue로 구현해보자.

 

 

📌 정답 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


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

        int answer = 0;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer> aPoint = new PriorityQueue<>((o1, o2) -> o2 - o1);
        PriorityQueue<Integer> bPoint = new PriorityQueue<>((o1, o2) -> o2 - o1);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < a; i++) {
            aPoint.offer(Integer.parseInt(st.nextToken()));
        }


        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < b; i++) {
            bPoint.offer(Integer.parseInt(st.nextToken()));
        }


        if (n % 2 == 1 && !aPoint.isEmpty()) {
            answer += aPoint.poll();
        }

        for (int i = 0; i < n / 2; i++) {
            int tmpA = 0;
            int tmpB = 0;
            if (aPoint.size() >= 2) {
                int aFirst = aPoint.poll();
                int aSecond = aPoint.poll();
                tmpA = aFirst + aSecond;
                aPoint.offer(aFirst);
                aPoint.offer(aSecond);
            }
            if (bPoint.size() >= 1) {
                tmpB = bPoint.peek();
            }

            if (tmpA > tmpB) {
                answer += tmpA;
                aPoint.poll();
                aPoint.poll();

            } else {
                answer += tmpB;
                bPoint.poll();
            }
        }
        System.out.println(answer);
    }
}