24337 가희와 탑 [JAVA]

문제분석

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

맨 왼쪽에서 봤을때 보이는 빌딩의 수 a

맨 오른쪽에서 봤을때 보이는 빌딩의 수 b

그리고 전체 빌딩의 수 n 가 주어진다. 

 

이때 만들 수 있는 빌딩 높이 배열 중 사전순으로 가장 빠른 높이 배열을 찾아 출력하는 문제다.

 

문제를 조금 나누어 생각해보면

a < b인 경우, a == b인 경우, a > b인 경우로 나눠진다

 

맨 왼쪽에서 a개의 빌딩을 보는 높이 배열 중 가장 사전 순으로 빠른 경우는

1 ... 1 2 3 .. a 이다.

 

반대로 맨 오른쪽에서 b개의 빌딩을 보는 가장 사전 순으로 빠른 경우는 

1 .. 1 b b-1 b-2 .. 1이다.

 

하지만 a != b인 경우  1 .. 1 2 .. a b ... 1의 배열로 빌딩이 서있을 때

왼쪽 또는 오른쪽에서 보이는 빌딩의 갯수가 각각 a+1개 혹은 b+1개가 된다.

 

또, a==b인 경우에도 1 ...1 2 ... a b ... 1보다 1 ... 1 2 ... a ...1이 사전순으로 더 빠르다.

 

즉, 우리는 양쪽 모두를 고려해야 하기에 Max(a,b)를 가장 뒤로 보낼 수 있는 방법으로 배열을 구성해야 한다.

 

방식은 단순하다.

 

항상 1이 앞에 많이 쌓여야 좋고, MaxHeight은 뒤로갈수록 좋다.

 

그렇기에 MaxHeight을 포함하여 a개의 빌딩 앞에 높이가 1인 빌딩을 가능한 최대로 배치하고

그 다음, 1부터 a-1개만큼 높이를 높여가며 빌딩을 추가해주면 왼쪽에서 봤을 때 a개의 빌딩이 보이게 된다.

 

반대로, MaxHeight포함하여 b개의 빌딩을 만들기 위해선 MaxHeight빌딩 오른쪽부터 b-1개의 빌딩을 배치하면 된다.

 

여기서, 주의할 점은

n=10일때

a=1, b=5

a=1, b=10

a=10, b=1

이런 경우를 생각해보면 무작정 maxHeight을 뒤로 배치하면 왼쪽에서 보이는 빌딩이 1개가 아닌 2개가 되는 경우, maxHeight빌딩이 배치되지 않는 경우가 발생할 수 있다.

 

따라서, 만약 a=1인 경우 maxHeight은 맨 앞에 배치되어야 한다.

그렇기에 b개의 빌딩을 배치하는 경우에도 maxHeight이 이미 배치된 경우 원래 maxHeight을 배치할 곳에 1을 넣고 그 뒤에 b-1개의 빌딩을 세워야 한다.

 

코드

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();
        if(a+b-1 > n){
            System.out.println("-1");
            return;
        }

        int maxHeight = Math.max(a,b);
        int firstBuildings = n - (a+b-1);

        boolean isMaxExist = false;
        for (int i = 0; i < firstBuildings; i++) {
            if(a == 1 && i == 0){
                System.out.print(maxHeight+" ");
                isMaxExist = true;
            }else{
                System.out.print(1+" ");
            }
        }

        for (int i = 0; i < a - 1; i++) {
            System.out.print((i+1)+" ");
        }

        if(isMaxExist){
            System.out.print(1);
        }else{
            System.out.print(maxHeight);
        }

        for (int i = 0; i < b - 1; i++) {
            System.out.print(" "+(b-1 - i));
        }
    }

}