[백준]18320. 2xN 예쁜 타일링(JAVA)

이번에 풀어 볼 문제는 < 백준 18320번. 2xN 예쁜 타일링 > 이다.

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

📌 문제 탐색하기

목표

얻을 수 있는 예쁨의 최댓값 구하기

해야 할 것

1. 예쁨이 최대가 되게 하려면 타일을 어떻게 배치해야 할까?

입력

[첫 줄] 정수 N ( 화장실 바닥의 가로 길이), A (2x1 크기의 타일 개수), B(2x2 크기의 타일 개수)

( 1 ≤ N, A, B ≤ 2000 , 2 × B + A ≥ N )

[둘째 줄] 2x1 크기 타일의 예쁨 ( 각 예쁨 은 10^6 이하 정수 )

[셋째 줄] 2x2 크기 타일의 예쁨  ( 각 예쁨 은 10^6 이하 정수 )

출력

얻을 수 있는 예쁨의 최댓값

아이디어

1.예쁨이 최대가 되게 하려면 타일을 어떻게 배치해야 할까?

 

사용할 2x1 크기 타일의 개수를 a, 2x2 크기 타일이 개수를 b 라고 하면,

a + 2b = N 이 되어야 한다.

 

예제 1의 경우는 a + 2b = 5 가 되어야 한다.

이때 가능한 a,b 의 조합은 다음과 같다.

1) b=1일때, a = 3

2) b=2일때, a = 1

 

따라서 예쁨의 최대를 계산하려면,

1) 의 경우는 ' 2x2 크기 타일 중 예쁨이 가장 큰 값 1개 + 2x1 크기 타일 중 예쁨이 가장 큰 값 3개' 를 구하고,

2) 의 경우는 '2x2 크기 타일 중 예쁨이 가장 큰 값 2개 + 2x1 크기 타일 중 예쁨이 가장 큰 값 1개' 를 구하면 된다.

이후 1) 과 2) 중 더 큰 값이 얻을 수 있는 예쁨의 큰 최대값이 된다.

 

 즉, 가능한 a,b의 조합을 먼저 뽑아낸 뒤

2x1 크기 타일 중 예쁨이 가장 큰 값 a 개 , 2x2 크기 타일 중 예쁨이 가장 큰 값 b 개를 뽑아 더하면 해당 조합으로 얻을 수 있는 예쁨의 최대값이 된다.

각 조합에서 계산된 최대값 중 가장 큰 값이 결과적으로 전체 예쁨의 최대값이 된다.

📌 코드 설계하기

1. input 입력을 받는다.

2. 가능한 a,b 조합을 뽑고, 2x1 크기 타일 중 예쁨이 가장 큰 값 a 개 , 2x2 크기 타일 중 예쁨이 가장 큰 값 b 개를 뽑아 더한다.

3. 2번에서 나온 각 조합의 결과값 중 가장 큰 값이 전체 예쁨의 최대값이 된다.

📌 정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

        int N = Integer.parseInt(firstLine[0]);
        int A = Integer.parseInt(firstLine[1]);
        int B = Integer.parseInt(firstLine[2]);
        int resultMax = 0;

        String[] secondLine = br.readLine().split(" ");
        String[] thirdLine = br.readLine().split(" ");

        List<Integer> twoByOne = new ArrayList<>();
        List<Integer> twoByTwo = new ArrayList<>();

        for(int i =0; i<A; i++){
            int tile = Integer.parseInt(secondLine[i]);
            twoByOne.add(tile);
        }

        for(int i =0; i<B; i++){
            int tile = Integer.parseInt(thirdLine[i]);
            twoByTwo.add(tile);
        }

        twoByOne.sort(Collections.reverseOrder()); // 내림차순 정렬
        twoByTwo.sort(Collections.reverseOrder());


        for(int b = 0; b<=B; b++){
            if(2*b>N){
                break;
            }

            int a = N - 2*b;

            if(a>A){
                continue;
            }

            int max = 0;

            // 예쁨 최대값 계산
            for(int i=0; i<a; i++){
                max+=twoByOne.get(i);
            }

            for(int i=0; i<b; i++){
                max+=twoByTwo.get(i);
            }

            resultMax = Math.max(resultMax,max);

        }

        System.out.println(resultMax);
    }

 

➡️sort() 메서드로 리스트를 정렬하는데 필요한 시간복잡도는 O(NlogN)이다. 

➡️따라서 정렬에 필요한 시간복잡도는 O(AlogA) + O(BlogB) 가 된다.

 

➡️ 가능한 a,b 조합을 찾는 외부 for 문의 최대 연산 횟수는 B번이다.

➡️ 내부에서 실행될 수 있는 for문의 최대연산 횟수는 a+b 인데, a+2b = N이므로 a+b는 N보다 작다. 그러므로 내부에서 실행되는 for문의 연산횟수는 N 보다 작을 것이다.

➡️ 따라서 전체 for문의 시간복잡도는 O(B*N) 보다 작은 값이 될것이다.

 

➡️결론적으로 전체 시간복잡도는 대략 O(AlogA) + O(BlogB) +O(B*N) 으로 나타낼 수 있는데 이때, A,B,N의 최대값은 모두 2000이다. log2000 = 약 11으로 칠때, 2000*11 + 2000*11 + 2000*2000 = 22000+22000+4000000 = 4044000 이므로 전체 연산횟수는 주어진 시간 범위를 초과하지 않는다. 

📌 알게 된 것

리스트를 오름차순 정렬할 때는,

List.sort();

 

내림차순 정렬할 때는

List.sort(Collections.reverseOrder());

 

를 사용해준다.