[백준 18230번] 2xN 예쁜 타일링 - (java)

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

 

📌 문제 탐색하기

 

2x1 타일을 사용하면 90도로 회전을 하든 안하든 2x1 을 반드시 2개 사용해야 한다. 따라서 N이 짝수일때는 2x1 타일 2개와 2x2 타일 1개 중에서 더 값이 큰것을 선택하면 되고, N이 홀수일때는 2x1 타일이 반드시 하나 들어가야 한다.

무조건 가장 큰 값부터 선택을 하는게 좋기때문에 2x1과 2x2 타일을 정렬해서 가장 큰 값부터 사용한다.

📌 코드 설계하기

두개의 배열을 선언하고 각각 2x1 크기 타일과 2x2 크기 타일을 넣고 정렬한다.

홀수일때는 무조건 먼저 2x1 타일중 값이 가장 큰 타일을 하나 선택한다.

가로 길이 N을 다 채울때 까지 남아있는 2x1 타일중 가장 값이 큰 타일 2개와 2x2 타일 중에서 값이 가장 큰 타일의 값을 비교하여

더 큰것을 선택하는 일을 반복한다.

 

📌 코드

import java.util.Arrays;
import java.util.Scanner;

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();
		int result = 0;

		int[] arr1 = new int[A];
		int[] arr2 = new int[B];

		for (int i = 0; i < A; i++) {
			arr1[i] = sc.nextInt();
		}

		for (int i = 0; i < B; i++) {
			arr2[i] = sc.nextInt();
		}

		Arrays.sort(arr1);
		Arrays.sort(arr2);

		int a = A-1;
		int b = B-1;

		if (N % 2 == 1) { // 홀수
			// 2x1 타일 하나 선택
			result = arr1[a];
			a -= 1;
			N-=1;

		}
		while(N>0){
			int sum1 = 0;
			int sum2 = 0;
			if((a)>=0 && (a-1)>=0){
				sum1 = arr1[a] + arr1[a-1];
			}
			if(b>=0){
				sum2 = arr2[b];
			}
			if(sum1>sum2){
				result +=sum1;
				a-=2;
			}else{
				result+=sum2;
				b-=1;
			}
			N-=2;

		}
		System.out.println(result);
	}
}