문제
일직선. 다양한 높이의 건물 n개 존재.
가희는 건물의 왼쪽에, 단비는 건물의 오른쪽에
가희, 1번 건물, 2번 건물 ... n번, 단비
현재 위치의 건물보다 왼쪽에 있는 건물들이 모두 현재 위치 건물보다 높이 작으면
가희는 현재 위치 건물 볼 수 있음
현재 위치 건물보다 오른쪽에 있는 건물들이 모두 현재 위치보다 높이가 작으면
단비는 현재 위치 건물 볼 수 있음
두 사람이 볼 수 있는 건물의 개수가 주어질 때,
N개의 건물 높이 중 사전 순으로 가장 앞선 것 ??
내 코드
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
# 일직선. 다양한 높이의 건물 n개 존재.
# 가희는 건물의 왼쪽에, 단비는 건물의 오른쪽에
# 가희, 1번 건물, 2번 건물 ... n번, 단비
# 현재 위치의 건물보다 왼쪽에 있는 건물들이 모두 현재 위치 건물보다 높이 작으면
# 가희는 현재 위치 건물 볼 수 있음
# 현재 위치 건물보다 오른쪽에 있는 건물들이 모두 현재 위치보다 높이가 작으면
# 단비는 현재 위치 건물 볼 수 있음
# 두 사람이 볼 수 있는 건물의 개수가 주어질 때,
# N개의 건물 높이 중 사전 순으로 가장 앞선 것 ??
n,a,b = map(int, input().split()) # 건물 개수, 가희가 볼 수 있는 a개, 단비가 볼 수 있는 b개
# 1~(a-1) ~ max(a,b) ~ (b-1) ~ 1
res = deque()
for i in range(1,a):
res.append(i)
res.append(max(a,b))
for i in range(b-1, 0, -1):
res.append(i)
if len(res) > n:
print(-1)
else:
temp = res.popleft() # 가장 첫번째 꺼 일단 꺼낸 다음에
for _ in range(n - len(res) - 1): # 일단 한개 뺏으니까 그거만큼 반영
res.appendleft(1)
res.appendleft(temp)
print(*res)코멘트
먼저 건물의 수 N은 고려하지 않고 조건만 보면,
왼쪽부터 건물이 1부터 a까지 오른차순으로 있고, 또 그 옆에 b부터 1까지 내림차순으로 있으면 된다.
a=3, b=3인 경우 1 2 3 2 1이런 식으로 있는게 조건을 만족시키는 가장 간단한 경우이다.
다만 a와 b중 더 작은 높이의 건물은 존재하면 안된다.
-> a=3, b=2 인 경우 1 2 3 1이어야 한다.
즉, 높이가 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까지의 건물을 세우면 된다 !
이제 여기서 N을 생각해보면, 필수적으로 세워야 하는 건물의 수가 N보다 크면 조건을 만족할 수 없으니 -1을 출력하고 끝내면 된다.
하지만 건물의 수보다 N이 크다면 이미 세워 놓은 건물을 안 해치면서 사전상 가장 앞서는 방법을 생각해야 한다.
-> 사전상 가장 앞서는 방법을 생각해야 한다. 그렇다는 건 결국 1을 가장 왼쪽에서 필요한 만큼 낑겨 넣어야 한다는 뜻.
다시 풀어봄
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
# 가희와 탑
# 일직선 상 다양한 높이의 건물들이 N개 존재.
# 가희는 건물의 왼쪽, 단비는 건물의 오른쪽.
# 건물을 볼 수 있는 규칙 :
# 1. 가희 기준 : 1번 건물부터 -> 오른쪽 방향으록 건물을 보는데.
# 1-1. k번 건물보다 왼쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면, 가희는 k번 건물을 볼 수 있다.
# 2. 단비 기준 : n번 건물부터 <- 왼쪽 방향으로 건물을 보는데.
# 2-1. k번 건물보다 오른쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면 단비는 k번 건물을 볼 수 있다.
### **** 예외 상황을 잘 체크했어야 함. *****
# 초기 조건 : 건물 개수 n, 가희가 볼 수 있는 건물 개수 a, 단비가 볼 수 있는 건물 개수 b가 주어진다.
# 사전 순으로 가장 앞서는 N개의 건물 높이 정보 출력
# 결국 일단 a-1, b-1개씩은 무조건 작성해야 한다고 생각했어야 함. (사전 순)
# 그리고 a,b MAX 값을 중간에 세워두기... 물론 개수가 남으면 1로 채워야함.
# *** 예외로 만약 a가 MAX인 경우 ! 그 예외를 위해 맨 앞에 값을 미리 빼두고, 1로 채운 후에 다시 넣어주면 해결
# N <= 10,000 이라서 N^2 안됨
n,a,b = map(int, input().split())
dq = deque()
for i in range(1,a): # 가희에 대해서
dq.append(i)
dq.append(max(a,b)) # 둘 중 MAX 값으로
for i in range(b-1, 0, -1): # 단비에 대해서 (b-1 ~ 1)
dq.append(i)
# 예외 생각
if n < len(dq): # 불가능
print(-1)
else:
temp = dq.popleft()
for _ in range(n - len(dq) -1):
dq.appendleft(1)
dq.appendleft(temp)
print(*dq)왜 마지막에 temp를 뺀 이후에 1을 추가 후 맨 앞에 넣어줬냐고 묻는다면...
예외 상황으로 a가 MAX인 경우 ! 이 경우 가희는 1개만 볼 수 있어야 하는데, n > len(dq)인 상황이면 앞에 1을 삽입해줘야 함. 그냥 삽입하면 2개를 볼 수 있게 되므로, 미리 빼준 후에 넣어줬어야 함.
