[백준 24337 🥇] 가희와 탑

문제

일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다.

• 가희의 오른쪽에는 1번 건물이 있습니다.
• x가 1이상 N-1이하의 정수일 때, x번 건물의 오른쪽에는 x+1번 건물이 있습니다.
• N번 건물의 오른쪽에는 단비가 있습니다.

가희와 단비가 볼 수 있는 건물은 아래와 같습니다.

• 가희는 1번 건물을 볼 수 있습니다.
• k번 건물보다 왼쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면, 가희는 k번 건물을 볼 수 있습니다.
• 단비는 N번 건물을 볼 수 있습니다.
• k번 건물보다 오른쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면, 단비는 k번 건물을 볼 수 있습니다.

예를 들어, N이 3이고, 1번 건물의 높이가 1, 2번 건물의 높이가 3, 3번 건물의 높이가 2라고 하겠습니다.

가희가 볼 수 있는 건물과 단비가 볼 수 있는 건물의 수는 각각 2개입니다. 이를 각각 노란색, 연보라색으로 표시하겠습니다.

가희가 3번 건물을 볼 수 없는 이유는 3번 건물 왼쪽에 있는 2번 건물의 높이가 3번 건물보다 높기 때문입니다. 그리고, 단비가 1번 건물을 볼 수 없는 이유는 1번 건물보다 오른쪽에 있는 2번 건물과 3번 건물이 1번 건물보다 높기 때문입니다.

가희와 단비 사이에 있는 건물의 개수 N과 가희가 볼 수 있는 건물의 개수 a, 단비가 볼 수 있는 건물의 개수 b가 주어집니다. 사전 순으로 가장 앞서는 N개의 건물 높이 정보를 출력해 주세요.

입력

첫째 줄에 건물의 개수 N, 가희가 볼 수 있는 건물의 개수 a, 단비가 볼 수 있는 건물의 개수 b가 공백으로 구분해서 주어집니다.

출력

문제의 조건에 맞는 건물들의 높이 정보가 1개 이상 존재하는 경우 N개의 건물 높이 정보 중 사전순으로 가장 앞선 것을 출력해 주세요. 출력 형식은 다음을 만족해야 합니다.

• 1번 건물, ... , N번 건물의 높이를 공백으로 구분해서 출력해 주세요. 출력하는 수들이 모두 다를 필요는 없습니다.
• 높이는 1보다 크거나 같은 정수여야 합니다.

문제의 조건에 맞는 건물들의 높이 정보가 존재하지 않으면 첫 줄에 -1을 출력해 주세요.

문제풀이

import sys

n,a,b=map(int, sys.stdin.readline().split(' '))
# 건물의 최고 높이는 max(a,b)
maxheight=max(a,b)
# a-1까지 오름차순 + 최고 건물 높이 + b-1부터 내림차순
buildings=list(range(1,a))+[maxheight]+list(range(b-1,0,-1))

# 만들어진 건물들의 개수가 n보다 크다면 불가능한 경우
if len(buildings)>n:
    print(-1)
    sys.exit(0)

# n보다 작다면 가희가 볼 수 있는 건물의 개수를 위반하지 않으면서 사전순으로 가장 앞쪽에 위치한 건물 배열을 만들기 위해서
# 1을 넣을 수 있는 만큼 왼쪽에 넣어준다
# 반례 : 3 1 2
while len(buildings)<n:
    buildings.insert(1,1)

for b in range(n):
    print(buildings[b], end=' ')

해결 아이디어만 도출하면 구현은 매우 쉬운 문제다!

• 먼저, 건물의 개수 n개를 만족하는 것은 배제하고 생각한 상태로, 가희가 볼 수 있는 건물의 개수가 a개, 단비가 볼 수 있는 건물의 개수가 b개인 사전순으로 가장 앞쪽에 위치하는 수열을 만들어보자
• a와 b 중 더 높은 수가 최고 건물 높이가 되고, 최고 건물 높이 왼쪽으로는 1부터 a-1까지 오름차순인 배열, 오른쪽으로는 b-1부터 1까지 내림차순인 배열이 위치하면 a,b를 만족하는 수열이 만들어진다.
• = [1부터 a-1까지 오름차순 배열] + [최고 건물 높이] + [b-1부터 1까지 내림차순인 배열]
• 위 방식대로 수열을 만들어보면 아래와 같다.

• 이제 a와 b의 개수를 만족하면서 건물의 개수 n도 만족하려면 어떻게 해야할까?
• 우선 위 과정을 거쳐 만들어진 수열의 길이가 n보다 크다면, 그 값은 불가능한 값이므로 -1을 출력하고 프로그램을 종료한다.
• 수열의 길이가 n보다 작을 경우, a,b값을 만족하면서 사전순으로 가장 앞쪽에 위치하려면 맨 왼쪽 기준 오른쪽에 가장 작은 높이 값인 1을 수열의 길이가 n이 될 때까지 넣어주면 된다.