백준 24337 가희와 탑 - 파이썬

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

24337번: 가희와 탑

 

 

 

왼쪽에 가희, 오른쪽에 단비가 있고, 인간과 건물 사이에 그 건물보다 작은 건물만 있어야 해당 건물을 볼 수 있다. 같은 것도 못본다.

 

먼저, 건물의 수인 N은 고려하지 않고 조건만 만족시켜 보자.

 

이 조건만을 만족시키는 것은 간단하다.

왼쪽부터 건물이 1부터 a까지 오름차순으로 있고, 또 그 옆에는 b부터 1까지 내림차순으로 있으면 된다.

a = 3, b = 3인 경우에는 건물이 1 2 3 2 1 이런 식으로 있는 게 조건을 만족시키는 가장 간단한 경우이다.

 

다만, a와 b 중 더 작은 높이의 건물은 존재하면 안된다.

이게 무슨 소리냐면, a = 3, b = 2인 경우 1 2 3 2 1 이 아니라 1 2 3 1 이어야 한다.

1 2 3 2 1 이면 오른쪽에서 봐도 건물이 3개나 보인다. a > b이므로 내림차순 건물 중 높이가 b인 건물을 지워줘야 사전 순 가장 앞서면서 조건을 만족한다.

사실 a와 b가 같아도 마찬가지이다. a = 3, b = 3인 경우에서 1 2 3 3 2 1도 조건은 만족하지만 1 2 3 2 1이 더 간단하다.

 

그러기 위해서는 1 ~ (a-1) 까지 건물을 세우고, max(a, b) 높이의 건물을 세운 뒤, (b-1) ~ 1 까지의 건물을 세우면 된다.

 

 

여기까지만 구현한 예시를 찾아보자면

a = 3, b = 1의 경우 1 2 3,

a = 3, b = 2의 경우 1 2 3 1,

a = 3, b = 5의 경우 1 2 5 4 3 2 1,

a = 1, b = 4의 경우 4 3 2 1

 

정도가 있을 수 있다.

 

 

 

이제 여기서 N을 추가해 본다.

 

만약 필수적으로 세워야 하는 건물의 수가 N보다 크다면 조건을 만족시킬 수 없으니 -1을 출력하고 떠나면 된다.

하지만 건물의 수보다 N이 크다면 이미 세워 놓은 건물을 안 해치면서 사전상 가장 앞서는 방법을 생각해야 한다.

 

1은 사전순 정렬할 때 제일 앞에 오는 수이면서, 맨 왼쪽이나 오른쪽에 있지 않는 이상 다른 건물에 가려서 보이지 않는다.

따라서 이 문제의 핵심은 1을 안보이는 한 제일 왼쪽에 낑겨넣기가 되겠다.

그리고 이를 다 만족하면서 언제나 아무도 못보는 위치는 맨 왼쪽 건물의 오른쪽이다.

 

위의 예시에 N = 6이라는 조건을 추가해보면

a = 3, b = 1의 경우 1 1 1 1 2 3,

a = 3, b = 2의 경우 1 1 1 2 3 1,

a = 3, b = 5의 경우 -1,

a = 1, b = 4의 경우 4 1 1 3 2 1

 

이렇게 맨 왼쪽 건물 오른쪽에 1을 수에 맞게 추가해주면 된다.

세 번째 케이스는 건물의 수가 7개가 되어 조건을 만족시킬 수 없다.

 

 

N, a, b = map(int, input().split())
answer = []

# N 고려 안하고 제일 간단하게 조건 만족시키기
for i in range(1, a):
    answer.append(i)
answer.append(max(a, b))
for i in range(b-1, 0, -1):
    answer.append(i)

if len(answer) > N: # 조건이 만족이 안되는 경우
    print(-1)
else:
    print(answer[0], end=" ")
    for i in range(N-len(answer)): # 핵심 포인트
        print(1, end=" ")
    for i in range(1, len(answer)):
        print(answer[i], end=" ")

 

 

문제를 잘못 이해해서 좀 헤맸었다.

이렇다 할 알고리즘이 없는 문제가 골드인 이유가 있었다.