BOJ 18230 2 X N 예쁜 타일링(Java)

문제 탐색하기

• 각 타일의 예쁨 정도 배열이 정수로 들어온다.
  •  N, A, B(1 ≤ N, A, B ≤ 2000, 2 × B + A ≥ N)

• 각 타일의 예쁨은 1,000,000 이하의 양의 정수이다.

• 정답으로 가능한 최대 값은 2000 Χ 1,000,000 = 2,000,000,000 으로 정수 범위 이내이다.

코드 설계하기

구현 방법

• A 타일 입력과 B 타일 입력을 각각 정렬을 수행한다.
  • N이 홀수인 경우 반드시 2 Χ 1 타일을 사용하게 되므로, A 타일을 우선적으로 사용한 후 나머지 타일 배치를 수행한다.
• 각 타일에 의해 정답으로 더해질 수 있는 후보값을 계산한다.
  • 둘 중 큰 값을 정답 값 더해준다.
  • N의 길이를 2만큼 줄인 후 동일 연산을 수행한다.
  • N이 0이 될 때까지 반복한다.
• 매 순간에 대해 최적 해를 구한다. => Greedy Algorithm

시간 복잡도

• 정렬에 의한 복잡도가 O(A log A), O(B log B) 이므로 O(N log N)에 근접한다.
  • N 최댓값이 2,000이므로 약 22,000 정도이며, 시간 내 풀이가 가능하다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class b18230 {  
    private static int N, A, B, answer;  
    private static int[] tile_A;  
    private static int[] tile_B;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());  
        A = Integer.parseInt(st.nextToken());  
        B = Integer.parseInt(st.nextToken());  
        tile_A = new int[A];  
        tile_B = new int[B];  
  
        st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < A; i++) {  
            tile_A[i] = Integer.parseInt(st.nextToken());  
        }  
  
        st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < B; i++) {  
            tile_B[i] = Integer.parseInt(st.nextToken());  
        }  
  
        // 정렬 수행  
        Arrays.sort(tile_A);  
        Arrays.sort(tile_B);  
  
  
        // 값이 홀수인 경우, A 타일을 우선적으로 사용 후 남은 타일을 배치한다.  
        int a_i = A - 1, b_i = B - 1;  
        if (N % 2 != 0) {  
            answer += tile_A[a_i--];  
            N--;  
        }  
  
        while (N != 0) {  
            int tmpA = 0, tmpB = 0;  
  
            // 배치 가능 여부를 확인 후,  
            // A 타일의 value와 B 타일의 value를 계산한다.  
            if (a_i >= 1){  
                tmpA = tile_A[a_i] + tile_A[a_i - 1];  
            }  
            if (b_i >= 0){  
                tmpB = tile_B[b_i];  
            }  
  
            if (tmpA >= tmpB){  
                answer += tmpA;  
                a_i -= 2;  
            }else {  
                answer += tmpB;  
                b_i--;  
            }  
  
            N -= 2;  
        }  
  
        System.out.println(answer);  
  
    }  
}