서론-쓸데없는 말.
2주차 27문제 중 세 문제가 플래티넘급이었다.
그 중에 히스토그램과 가장 가까운 두 점은 PS 대부 백준님이 제시한 두시간 이내에 변변찮은 풀이법 조차 생각해내지 못하여 결국 답을 보고 말았다. 그런데 답을 보니 내가 생각하던 아이디어에서 크게 벗어나지를 않았다는 것을 알고 굉장히 아쉬웠다.
그래서 마지막 남은 플딱 문제는 자력으로 풀고 말겠다 결심을 하게 됐다.
그리고 금요일 밤부터 시작해서 일요일 아침까지 계속 생각하다 결국 풀었다.
기본적인 아이디어
전제조건:
1. 교차하는 원은 존재하지 않는다.
2. 원들은 모두 붙어있다.
관찰을 통해 알게된 것:
1. 원에 의해 생기는 영역의 개수는 기본적으로 원의 개수와 동일하다.
2. 예외 상황으로 원 내부에 원이 꽉 차게 될 경우 원 개수에 더하기 1을 한 만큼 영역이 생긴다.( 원 내부의 모든 원의 반지름의 합이 원의 반지름과 같다면 원 내부의 원이 원을 가득 채웠다는 의미가 된다.)
입력으로 원의 개수가 주어지기에, 결국 예외상황이 몇번이나 나타나는 지만 구하면 되는 것이었다.(하지만 나는 원의 개수까지 계속 카운팅 하도록 만들었다. 지금 생각해보니 왜 그랬는지 모르겠다.)
풀이법
1. 동적 계획법
처음으로 생각했던 방법은 동적 계획 법이었다. 분할 정복을 이용해서 문제를 풀겠다는 아이디어였다.
주어진 입력값을 X값을 기준으로 정렬하여, 모든 원에 대해서 원 안의 영역 개수를 탐색하고, 탐색 된 원은 DP에 저장하여 탐색 했던 원이 또 다시 탐색되며 카운팅 되는 것을 방지하자는 생각이었다.
그런데 입력 조건이 너무 커서 왠지 그런 식으로 하면 메모리 초과가 날 것 같았다. 그래서 시도도 안했다.
2. 스택
다음으로 생각한 방식은 스택을 이용한 방식이었다.
원을 마치 괄호처럼 생각하고, 원이 열리고 닫힐 때 원을 하나 카운팅 해주면 가장 작은 원을 셀 수 있게 된다.
그렇게 가장 작은 원을 세고 나면, 그 정보를 스택에 그대로 저장하여, 다음 원이 닫힐 때에 그 정보를 이용할 수 있도록 해주면, 원 안의 모든 원의 반지름의 합이라던지, 아니면 원 안에 중첩된 수많은 원들의 갯수라던지 그런 것들을 입맛대로 써먹을 수 있게 된다.
import sys
input = sys.stdin.readline
N = int(input())
circles = [list(map(int, input().split())) for _ in range(N)]
def change_to_coord(circles):
coords = [0]*(N*2)
for i in range(len(circles)):
circle = circles[i]
open_coord = circle[0] - circle[1]
close_coord = circle[0] + circle[1]
coords[i] = ([open_coord, "o"])
coords[-1-i] = ([close_coord, "c"])
coords.sort(key=lambda x: (x[0], x[1]))
return coords
def solve(circles):
coords = change_to_coord(circles)
stack = []
for coord in coords:
if not stack:
stack.append(coord)
continue
if coord[1] == "c":
val = stack.pop()
circle_info = [1, 0]
inner_circle = val
while stack and isinstance(inner_circle[1], int):
circle_info[0] += inner_circle[0]
circle_info[1] += inner_circle[1]
inner_circle = stack.pop()
closer = inner_circle
radius = coord[0] - closer[0]
if circle_info[1] == radius:
circle_info[0] += 1
else:
circle_info[1] = radius
stack.append(circle_info)
else:
stack.append(coord)
result = 0
for info in stack:
result += info[0]
print(result + 1)
solve(circles)
후기
숫자야구 문제를 처참하게 틀리고서 절실히 느꼈던건, 문제가 기본적으로 어떤 문제인지 파악하는 것이 굉장히 중요하다는 것이다. 나는 숫자 야구 문제를 규칙을 만드는 문제라고 생각했던 반면, 푼 사람들은 그 문제를 하나의 값이 원하는 조건에 부합하는지 확인하는 문제로 받아들였다는 데에 차이가 있었다.
그래서 이번 문제에 접근 할 때, 이 문제가 기본적으로 어떤 문제인가 생각하는데 꽤 오랜 시간을 들였다. 거의 하루 반, 토요일은 노는 날이니까 그 정도 시간을 들여도 괜찮았다.
기하학적인 문제라는 관점에서 벗어나, 단순한 괄호문제라고 받아들이자, 주어진 입력을 괄호형식으로 바꿀 수 있었고, 그게 시작이었다.
지금이야 문제번호 옆에 떡하니 스택 이라고 써져있으니 스택을 어떻게 써먹을까 고민하다 답을 찾을 수 있었지만, 아마 그런 것 없이 했으면, 결국 답지를 봤을 것이다.
하지만 문제를 많이 풀다보면 결국 문제를 보는 눈도 생기지 않을까 생각한다. 그러니까 공부를 하겠지.
기분이 굉장히 좋다. 히스토그램과 가장 가까운 두점, 그리고 저번 주 최장공통문자열까지 플래티넘 문제에 모두 실패하여, 큰 스트레스를 받고 있었는데, 운좋게 한 문제 풀어서 자신감도 다시 좀 가질 수 있겠다.
다만 코드 자체가 너무 더러워서 좀 화난다. 스택 고수들 코드 좀 보면서, 스택 문제를 풀 때 대략 어떤 프레임으로 코드를 짜는 지 확인 해봐야겠다.
