백준 24025 돌의 정령 줄세우기 문제 풀이
백준 24025 돌의 정령 줄세우기 문제 풀이
백준 온라인 저지, 24025번: 돌의 정령 줄세우기
도입
문제의 요구사항은 제시된 “시야 점수와 관련된 정수”의 조건에 충족되는 배치를 출력하는 것이다.
정령들이 가질 수 있는 시야 점수는 $j-i$로 정의된다. $A_i$가 음수라면 시야 점수는 $-A_i$로 정의되므로, 부호는 방향으로 생각할 수 있다. 돌정령이 오른쪽을 바라보므로, 양수는 오른쪽, 음수는 왼쪽으로 시야가 열려있음을 알 수 있다.
풀어보기
자신의 시야에 막힘이 없으면 시야 점수를 1e9로 정의한다라는 조건을 이용하면 다음의 전략을 취할 수 있다:
- Ai가 양수라면 시야에 막힘이 없도록 배치 (점수: $10^9$)
- Ai가 음수라면 시야가 바로 막히도록 배치 (점수: $1$)
모든 $A_i$가 양수인 경우, 위와 같이 내림차순으로 배치하여 모든 정령이 시야 점수 $10^9$를 가지도록 할 수 있다.
1
2
3
replace = [0] * n
for i in range(1, n):
replace[-i] = i
양수 $A_i$에 대해 이미 내림차순 배치하였으므로, 음수 $A_i$에 대해서 그림과 같이 양수 $A_i$ 사이에 음수 $A_i$를 배치하는 것은 처리를 복잡하게 할 수 있다.
따라서 음수 $A_i$는 앞쪽에 오름차순 배치하여 시야 점수를 $1$이 되도록 한다.
1
2
3
4
5
6
7
8
9
10
11
n = 5
requires = [2, -2, 4, 1, 2]
replace = [0] * n
incr, desc = 1, 0
for i in range(n):
if requires[-i] > 0:
replace[-i] = incr
incr += 1
else:
replace[-i] = desc
desc -= 1
1
replace[i] - desc + 1
음수 $A_i$에 대해서는 인덱스를 음수 범위에서 오름차순으로 나타나도록 배치 처리하고, 전체 음수 $A_i$에 대해 인덱스가 0 이상이 되도록 조정한다.