[JAVA] 백준 18230_2xN 예쁜 타일링

[문제링크]

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

📌 문제 탐색하기

화장실 타일을 새로 교체하는데 2x1 ,2x2크키의 타일을 가지고 입력받은 2xN타일을 채우는데 이때 각각 타일의 예쁨수 ? 가 최대인 경우의 수를 찾아서 출력하는 문제이다. 

📌 코드 설계하기

1. (2xN) 크기의 안에 들어갈 수 있는 타일의 개수가 최대인 경우를 찾고
2. 타일의 종류에 따라서 - 가장 큰 예쁨값의 타일부터 입력(이 과정에서 예쁨값이 큰 순서대로 정렬처리하는게 필요할거 같음)해서 더하면 예쁨값의 최대값을 구할 수 있지 않을까 ?

📌 가능한 시간복잡도 

1. 배열을 정렬처리해야하니까 O(Aloga + BlogB)
2. n개의 타일을 배치해야하니까 O(N) 
따라서, 가능한 시간복잡도는 1,2를 더한 O( N + Alog A + BlogB )입니다.

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();

        //2x1 타일을 입력받고 정렬
        for (int i = 0; i < A; i++) {
            arr1.add(sc.nextInt());
        }
        
        //2x2 타일을 입력받고 정렬
        for (int i = 0; i < B; i++) {
            arr2.add(sc.nextInt());
        }

        //내림차순으로 정렬
        Collections.sort(arr1, Collections.reverseOrder());
        Collections.sort(arr2, Collections.reverseOrder());
        
        int ans = 0;

        //N이 홀수일 경우 2x1 타일 중 가장 큰 값을 사용
        if (N % 2 == 1) {
            ans += arr1.get(0);
            arr1.remove(0);
            N--;
        }

        // 2x2 타일과 2x1 타일을 조합해 채워 나가며 탐색
        for (int i = 0; i < N / 2; i++) {
            int case1 = 0, case2 = 0;

            if (arr1.size() >= 2) {
                case1 = arr1.get(0) + arr1.get(1);
            }

            if (arr2.size() >= 1) {
                case2 = arr2.get(0); 
            }

            if (case1 > case2) {
                ans += case1;
                arr1.remove(0); 
                arr1.remove(0);
            } else {
                ans += case2;
                arr2.remove(0); 
            }
        }
        System.out.println(ans);
    }
}

 

📌 실수 포인트는 ?

그리디 방식으로 올바르게 타일을 두 개씩 사용하는 조건을 설정하고, N을 적절히 감소시키며, 홀수일 때 2x1 타일을 처리하는 부분을 주의해야함.!!!!