[백준/Java] 18230번 : 2xN 예쁜 타일링

🌵 문제 분석

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

 

2xN 크기의 격자를 2x1, 2x2 타일로 채울 때

얻을 수 있는 예쁨의 최댓값을 구하는 문제이다.

 

입력값 :

N(바닥 너비) A(2x1 타일 개수) B(2x2 타일 개수)

2x1 타일의 예쁨을 의미하는 정수 A개

2x2 타일의 예쁨을 의미하는 정수 B개

5 4 3
1 2 3 4
4 5 6

 

예제 1의 경우 2x5 바닥을 2x1타일 4개 (1 2 3 4), 2x2타일 3개 (4 5 6)로 채운다.

아래 그림처럼 타일링해야 예쁨 정도의 최댓값을 가질 수 있다.

 

🌵 구현 아이디어

🤔 예쁨 정도가 가장 큰 타일을 먼저 선택하기

무조건 예쁨 정도가 크다고 먼저 선택하면 안 된다.

 

반례 : 

5 5 3
3 3 3 3 3
4 3 3

이 경우 2x2 타일 1개보다 2x1 타일 2개를 선택하는 것이 더 유리하다.

따라서 2x2 타일 1개와 2x1 타일 2개를 비교해서 더 큰 경우를 선택해야 한다.

 

✅ 접근 방법

• 타일들을 예쁨 정도가 큰 순서대로 정렬하여 최대의 예쁨 정도를 가질 수 있게 한다.
• 바닥의 너비가 홀수일 경우 2x1 타일 중 가장 큰 값 1개를 먼저 선택하고 시작한다.
• 남은 2x2타일이 1개 이상, 2x1타일이 2개 이상일 때 :
  • 2x2 타일 1개와 2x1 타일 2개를 비교해서 예쁨 정도가 더 큰 경우를 선택한다.
• 남은 2x2타일이 1개 미만이고 2x1타일이 2개 이상일 때  :
  • 2x1 타일 2개를 선택한다.
• 남은 2x1타일이 2개 이상이고 2x1타일이 2개 미만일 때  :
  • 2x2 타일 1개를 선택한다.

👉🏻 예제 구해보기

5 4 3
1 2 4 6 
1 3 5

 

1️⃣ 타일 정렬하기

2x1 : 1 2 4 6

2x2 : 1 3 5

Java로 역순 구하기 번거로워서 오름차순 정렬 후 뒤에서부터 탐색할 거임

 

2️⃣ 타일 고르기

• 남은 바닥 공간 : 2x5
• 타일 바닥 너비가 홀수이므로 2x1 타일 1개를 먼저 선택하기 
  • 남은 타일 :
    • 2x1 : 6 4 2 1
    • 2x2 : 5 3 1
• 남은 바닥 공간 : 2x4
• 타일 비교 : 2x1 2개 (4+2) > 2x2 1개 (5) 이므로 4, 2고르기
• 남은 타일 :
  • 2x1 : 6 4 2 1
  • 2x2 : 5 3 1
• 남은 바닥 공간 : 2x2
• 2x1 타일이 2개 미만이므로 2x2 타일 한개 고르기
• 남은 타일 :
  • 2x1 : 6 4 2 1
  • 2x2 : 5 3 1
• 남은 공간 : 0 -> 탐색 종료

3턴 후 선택된 타일

3️⃣ 최댓값 출력

6+4+5+2=17 출력

🌵 시간 복잡도

타일 정렬하는 데 걸리는 시간 : Arrays.sort의 시간 복잡도 -> O(nlogn)

타일을 고르는 데 걸리는 시간 : 최대 2xn인 공간의 너비만큼 탐색하므로 O(n)

 

n은 최대 2,000이다. 전체 시간 복잡도는 O(nlogn)*O(n) = 2000*3*2000 = 약 1,000,000

따라서 제한 시간 (2초) 안에 연산 가능하다.

🌵 알고리즘

각 타일 선택 단계에서 예쁨 정도가 큰 것부터 선택하여 최종 해를 구하므로 그리디 알고리즘에 해당

🌵 오답 노트

• 2x1 2x2 타일이 2개 이상, 1개 이상 존재할 때 / 2x1타일만 2개 이상 존재할 때 / 2x2타일만 1개 이상 존재할 때 세 가지로 나누는 부분을 놓쳤다.
• 바닥 너비가 홀수일 때 2x1타일을 하나 선택하고 탐색을 시작하는 부분이 왜 필요한지 이유를 찾기 어려웠다.
  그냥 탐색하다가 너비가 1만큼 남으면 2x1타일을 하나 선택하면 되지 않나? 하고 while문 시작할 때 그렇게 조건문을 구현 했는데 아니었다. 너비가 홀수인 바닥을 모두 채우려면 2x1 타일 한 개가 꼭 포함되어야 하는데, 이미 앞에서 모든 2x1타일을 (짝수개만큼) 다 사용했다면 바닥을 다 채울 수 없기 때문에 2x1 타일 한 개를 시작할 때부터 선택해야 한다. 이 부분때문에 계속 틀렸음..

🌵 코드 설계

1. 입력값 받기
   1. int N, A, B
   2. int[] t1, t2에 2x1타일과 2x2타일 값을 저장
2. t1, t2 정렬
3. 바닥의 너비가 홀수일 경우 2x1 타일 중 가장 큰 값 1개를 선택
4. 타일 고르기 (while문)
   • 2x2타일이 1개 이상, 2x1타일이 2개 이상일 때 :
     
     • 2x1 타일 2개를 선택해 tile1에 저장
     • 2x2 타일 1개를 선택해 tile2에 저장
     • tile1, tile2 중 더 큰 값을 선택
     • 예쁨의 최댓값 업데이트
     • 다음으로 선택할 타일의 인덱스 갱신
     • 남은 바닥 공간 업데이트
   • 2x2타일이 1개 미만이고 2x1타일이 2개 이상일 때  :
     • 2x1 타일 2개를 선택해 tile1에 저장
     • 예쁨의 최댓값 업데이트
     • 다음으로 선택할 타일의 인덱스 갱신
     • 남은 바닥 공간 업데이트
   • 2x1타일이 2개 이상이고 2x1타일이 2개 미만일 때  :
     • 2x2 타일 1개를 선택해 tile2에 저장
     • 예쁨의 최댓값 업데이트
     • 다음으로 선택할 타일의 인덱스 갱신
     • 남은 바닥 공간 업데이트
5. 예쁨의 최댓값을 출력

🌵 정답 코드

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

public class Main{
    static int N, A, B;
    static int[] t1, t2;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        t1 = new int[A];
        t2 = new int[B];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<A; i++){
            t1[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<B; i++){
            t2[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(t1);
        Arrays.sort(t2);

        int leftSpace = N; //남은 바닥 공간
        int ans = 0; //최댓값 저장
        int idx1 = A-2; //t1의 인덱스 (2칸짜리 타일을 선택하는 위치)
        int idx2 = B-1; //t2의 인덱스 (1칸짜리 타일을 선택하는 위치)

        if(N%2 != 0){
            ans += t1[A-1];
            leftSpace -= 1;
            idx1 -= 1;
        }

        while(leftSpace>0){
            int tile1 = 0;
            int tile2 = 0;

            //2x1 타일이 2개 이상이고 2x2 타일이 1개 이상이면
            if(idx1+1 >= 1 && idx2 >= 0){

                tile1 = t1[idx1] + t1[idx1+1];
                tile2 = t2[idx2];

                if(tile1>=tile2){
                    ans += tile1; //예쁨의 최댓값 업데이트
                    idx1 -= 2; //다음으로 탐색할 인덱스 갱신
                    leftSpace -= 2; //남은 바닥 공간 업데이트
                }else {
                    ans += tile2;
                    idx2 -= 1;
                    leftSpace -= 2;
                }
            }else if(idx1+1 >= 1){
                //2x1 타일만 2개 이상 남아있을 때
                tile1 = t1[idx1] + t1[idx1+1];
                ans += tile1;
                idx1 -= 2;
                leftSpace -= 2;
            }else if(idx2 >= 0){
                //2x2 타일만 1개 이상 남아있을 때
                tile2 = t2[idx2];
                ans += tile2;
                idx2 -= 1;
                leftSpace -= 2;
            }else break;
        }
        bw.write(ans+"");
        bw.close();
    }
}