백준 24025 돌의 정령 줄세우기 문제 풀이
문제 파악하기
문제의 요구사항은 제시된 “시야 점수와 관련된 정수”의 조건에 충족되는 배치를 출력하는 것입니다.
오른쪽을 바라보고 있는 각 돌의 정령들이 가질 수 있는 시야 점수는 j-i로 정의되어있는데, 주의할 점은 입력으로 들어오는 값이 시야 점수는 아니라는 것입니다.
정의상 시야점수는 양수만 나타날 수 있으나, 예제 입력들을 확인하면 음수 값도 주어짐을 알 수 있습니다.
“Ai가 음수라면 시야점수는 -Ai”라고 표현한 데에서 시야 점수는 항상 양수이고 ±는 다른 의미를 가지고 있음을 파악합니다.
이어지는 지문에서 값 Ai가 양수라면 시야점수는 |Ai| 이상이 되게, 음수라면 |Ai| 이하가 되게 배치하면 된다는 언급으로 ±의 의미를 확인할 수 있습니다.
문제 풀어보기
자신의 시야에 막힘이 없으면 시야 점수를 1e9로 정의한다라는 조건을 주목할 필요가 있습니다.
이 조건에 기반하여 다음과 같은 전략을 취할 수 있기 때문입니다.
- Ai가 양수라면 시야에 막힘이 없도록 배치 (
1e9) - Ai가 음수라면 시야가 바로 막히도록 배치 (
1)
위 전략은 “양수는 이상, 음수는 이하가 되게 한다”라는 조건에 항상 부합하게 할 수 있습니다.
다시 정리해서 우선, Ai가 양수만 있을때 아래와 같이 배치할 수 있습니다.
이와 같은 배치는 쉽게 구현할 수 있습니다.
1
2
3
replace = [0] * n
for i in range(1, n):
replace[-i] = i
파이썬으로 간단하게 표현했는데, 어쨌든 뒤에서부터 증가하도록 작성합니다.
Ai에 음수가 포함되어있다면 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
따라서 위와 같이 모든 값이 유일하도록 작성합니다.
다만 키 값은 0 이하일 수 없으므로 출력 시 desc를 offset으로 사용해야 합니다.
1
print(replace[i] - desc + 1)
답안 구현
이 문제는 이해하는데 시간을 들여야 해서 어려운 문제이지, 풀이 과정이 어렵진 않은 것 같습니다.