문제 보기 · Level 5 · 2017 카카오코드 본선 · 정답률 1% · 푼 사람 75명 (2026-09-30 기준)1
문제
평면에 점 n개가 있고, x 좌표끼리, y 좌표끼리 겹치지 않는다. 가장 왼쪽 점 S는 가장 위쪽 점이기도 하고, 가장 오른쪽 점 E는 가장 아래쪽 점이기도 하다.
귀걸이는 축에 평행한 직사각형들의 사슬이다. 직사각형은 주어진 점 두 개를 왼쪽 위와 오른쪽 아래 꼭짓점으로 쓴다. 첫 직사각형의 왼쪽 위는 S, 마지막 직사각형의 오른쪽 아래는 E이고, 앞 직사각형의 오른쪽 아래가 다음 직사각형의 왼쪽 위다. 점마다 값 k가 있어서, 그 점을 오른쪽 아래로 쓰는 직사각형은 가로 + 세로가 정확히 k여야 한다.
처음 귀걸이 수와, 변화 n개를 하나씩 따로 적용한 뒤의 귀걸이 수를 1,000,000,007로 나눈 나머지로 돌려준다. 변화는 점 하나 더하기 [0, x, y, k] 또는 원래 점 하나 빼기 [1, x, y, 아무 값]이다.
- 2 ≤ n ≤ 100,000, 좌표는 −\(10^9\) ~ \(10^9\)
- 변화는 누적되지 않는다. S와 E는 처음 상태로 고정된다
- 더하는 점은 원래 점과 x, y가 겹치지 않는다
풀이
막히면 한 단계씩 펼친다. 점의 u = x − y로 둔다.
필요한 개념
동적 계획법: 귀걸이는 S에서 E로 가는 경로다. “S에서 이 점까지 오는 수”와 “이 점에서 E까지 가는 수”를 구해 두면, 점 하나를 빼거나 더할 때 바뀌는 수는 둘의 곱이다. 같은 u끼리 딕셔너리로 묶으면 이어질 수 있는 점이 x 구간 하나로 모인다. 구간 합은 누적 합과 이분 탐색으로 구한다.
셈의 기본 법칙: “S에서 이 점까지 오는 수”는 바로 앞 점이 누구인지로 경우를 겹치지 않게 나눠 더한다(합의 법칙). 위에서 말한 “둘의 곱”은 앞부분과 뒷부분을 하나씩 짝짓는 곱의 법칙이다.
나눗셈과 합동: 더하기·빼기·곱하기는 중간에 몇 번 나머지를 취해도 마지막 나머지가 같다. 그래서 경로 수와 누적 합을 모두 1,000,000,007로 나눈 나머지로만 들고 다녀도 답이 맞는다.
1단계 · 작은 예로 손으로 풀기
문제의 예시는 S(0, 4, k = 1), P(2, 2, k = 4), E(4, 0, k = 4)다.
- S → P: 가로 2 + 세로 2 = 4 = P의 k라 된다. P → E: 2 + 2 = 4 = E의 k라 된다. S → E는 4 + 4 = 8이라 안 된다. 처음 귀걸이는 S → P → E 하나다.
- (3, 3, k = 4)를 더하면 S → 새 점(1 + 3 = 4)과 새 점 → E(1 + 3 = 4)가 다 된다. 새 귀걸이가 하나 생겨 2다.
- (3, 1, k = 2)를 더하면 P → 새 점(1 + 1 = 2)은 되지만, 새 점 → E는 1 + 1 = 2 ≠ 4다. 그대로 1이다.
- P를 빼면 하나뿐인 귀걸이가 P를 지나 0이다.
답은 [1, 2, 1, 0]이다. 점 Q를 더하면 “S에서 Q까지 오는 수 × Q에서 E까지 가는 수”만큼 늘고, 점을 빼면 그 점을 지나는 만큼 준다.
2단계 · 가장 단순한 방법과 그 속도
점을 x 순서로 놓고, 점마다 앞의 모든 점을 보며 이어지는지 따지면 \(O(n^2)\)이다. n = 10만이면 50억 번이다. 변화마다 다시 세면 그 10만 배라 어림없다.
3단계 · 핵심 아이디어
- f와 g: f[P]는 S에서 P까지 오는 사슬 수, g[P]는 P에서 E까지 가는 사슬 수다. 처음 답은 f[E]다. 사슬은 오른쪽으로만 가니 한 점을 두 번 지나지 않는다. 그래서 점 R을 지나는 사슬은 f[R] × g[R]개다.
- R을 빼면 f[E] − f[R]·g[R]이다. S나 E를 빼면 이 값이 저절로 0이다.
- 새 점 Q를 더하면 f[E] + (Q로 들어오는 수) × (Q에서 나가는 수)다.
- 이어지는 조건을 한 줄로: P → Q가 되려면 x_P < x_Q, y_P > y_Q이고 (x_Q − x_P) + (y_P − y_Q) = k_Q다. 셋째 식은 u_P = u_Q − k_Q와 같다. u_P가 정해지면 y_P = x_P − u_P라, y_P > y_Q는 x_P > x_Q − k_Q가 된다. 그래서 Q의 앞 점은 “u가 u_Q − k_Q인 무리에서 x가 x_Q − k_Q와 x_Q 사이(양 끝 제외)”인 점들이다.
- f는 x 순서로: 점을 x가 작은 것부터 보면 앞 점은 이미 다 계산되어 있다. u별로 x 목록과 f의 누적 합을 쌓아 두면, 구간 합을 이분 탐색 두 번으로 구한다. P → Q 화살표는 늘 x가 커지는 쪽이라 사이클이 없고, x 순서가 곧 이 화살표들의 위상 정렬이다.
- g는 거꾸로 밀어 주기: x가 큰 점부터 본다. R의 g가 정해지면 R의 앞 점들(무리 u_R − k_R에서 이어진 x 구간)에 g[R]을 더해 준다. 구간에 한꺼번에 더하는 일은 차분 배열로 하고, 무리마다 큰 x 쪽부터 차분을 쌓아 읽는다. 한 점을 읽을 때는 그보다 오른쪽 점들이 이미 다 밀어 준 뒤다. 이 밀어 주기는 역전파의
grad +=와 같은 일이다. f[Q]가 앞 점 f의 단순 합이라 화살표마다 기울기가 1이고, 그래서 g[P]는 f[P]가 1 늘 때 f[E]가 느는 양이다. - 새 점 Q의 뒤 점: R이 Q 뒤에 오려면 u_R − k_R = u_Q이고 x_R − k_R < x_Q < x_R이다. 점들을 w = u_R − k_R로 묶고, 구간 (x_R − k_R, x_R)이 x_Q를 품는 R의 g를 더한다. “시작 < x_Q인 R의 g 합 − 끝 ≤ x_Q인 R의 g 합”이라 이분 탐색 두 번이다. k_R ≤ 0인 점은 앞 점이 있을 수 없어 뺀다.
- S, E 고정: 더한 점이 S보다 왼쪽·위에 있거나 E보다 오른쪽·아래에 있으면, 들어오는 수나 나가는 수가 0이라 답이 그대로다. S와 E를 새로 정하지 않는다.
4단계 · 코드 흐름
- 점을 x 순서로 정렬한다. S는 맨 앞, E는 맨 뒤 점이다.
- f: 앞에서부터, 무리 u − k에서 x가 (x − k, x)인 점의 f 합을 구한다(S는 1). 무리 u에 (x, f 누적 합)을 더한다.
- g: 뒤에서부터, 무리 u의 차분을 이 자리까지 쌓아 g를 읽는다(E는 1). 무리 u − k의 x 구간에 g를 밀어 준다.
- k > 0인 점마다 무리 u − k에 (x − k, g)와 (x, g)를 모아 정렬하고 누적 합을 만든다.
- 변화마다: 빼기는 f[E] − f·g, 더하기는 f[E] + (앞 점 f 합) × (뒤 점 g 합)을 나머지로 적는다.
5단계 · 파이썬 코드
from bisect import bisect_left, bisect_right
from collections import defaultdict
MOD = 1_000_000_007
def solution(n, point, query):
pts = sorted(tuple(p) for p in point) # x가 작은 것부터
s_xy, e_xy = pts[0][:2], pts[-1][:2] # S, E
gx = defaultdict(list) # u → x들
gf = defaultdict(lambda: [0]) # u → f의 누적 합
f = {}
for x, y, k in pts:
v = 1 if (x, y) == s_xy else 0
t = x - y - k # 앞 점이 가져야 할 u
if v == 0 and t in gx:
xs, pre = gx[t], gf[t]
v = (pre[bisect_left(xs, x)] - pre[bisect_right(xs, x - k)]) % MOD
f[(x, y)] = v
gx[x - y].append(x)
gf[x - y].append((gf[x - y][-1] + v) % MOD)
add = {u: [0] * len(xs) for u, xs in gx.items()} # 값 = 이 칸부터 끝까지 add의 합
run = {u: 0 for u in gx}
ptr = {u: len(xs) - 1 for u, xs in gx.items()}
g = {}
for x, y, k in reversed(pts):
u = x - y
i = bisect_left(gx[u], x)
a, r, p = add[u], run[u], ptr[u]
while p >= i: # 이 칸까지 차분을 쌓는다
r += a[p]
p -= 1
run[u], ptr[u] = r % MOD, p
v = 1 if (x, y) == e_xy else r % MOD
g[(x, y)] = v
t = u - k
if v and t in gx: # 앞 점 구간에 v를 밀어 준다
xs = gx[t]
lo, hi = bisect_right(xs, x - k), bisect_left(xs, x) - 1
if lo <= hi:
add[t][hi] += v
if lo >= 1:
add[t][lo - 1] -= v
total = f[e_xy]
starts, ends = defaultdict(list), defaultdict(list)
for x, y, k in pts:
if k > 0:
w = x - y - k
starts[w].append((x - k, g[(x, y)]))
ends[w].append((x, g[(x, y)]))
def prefix(items):
items.sort()
keys, sums = [], [0]
for key, val in items:
keys.append(key)
sums.append((sums[-1] + val) % MOD)
return keys, sums
starts = {w: prefix(v) for w, v in starts.items()}
ends = {w: prefix(v) for w, v in ends.items()}
answer = [total]
for kind, x, y, k in query:
if kind == 1: # 빼기
answer.append((total - f[(x, y)] * g[(x, y)]) % MOD)
continue
u, before, after = x - y, 0, 0
if u - k in gx: # 들어오는 수
xs, pre = gx[u - k], gf[u - k]
before = (pre[bisect_left(xs, x)] - pre[bisect_right(xs, x - k)]) % MOD
if u in starts: # 나가는 수
keys, sums = starts[u]
after += sums[bisect_left(keys, x)]
keys, sums = ends[u]
after -= sums[bisect_right(keys, x)]
answer.append((total + before * after) % MOD)
return answer
pre[bisect_left(xs, x)] - pre[bisect_right(xs, x - k)]: x가 x − k보다 크고 x보다 작은 점들의 f 합이다. 누적 합은 맨 앞에 0을 두어 한 칸씩 밀려 있다.add[t][hi] += v,add[t][lo - 1] -= v: “이 칸부터 끝까지의 합”으로 읽으니, lo ~ hi 칸에만 v가 더해진다.% MOD: 파이썬의 %는 음수에도 0 이상을 돌려준다. 다른 언어는 뺀 뒤 MOD를 더해야 한다.
6단계 · 실행 추적
S(0, 9, 0), A(2, 6, 5), B(3, 7, 5), C(5, 5, 4), D(6, 2, 4), F(7, 3, 8), E(9, 0, 5)에서 센다.
| 점 | u | 앞 점 무리 u − k | 앞 점 x 구간 | 앞 점 | f | g |
|---|---|---|---|---|---|---|
| S | −9 | — | — | — | 1 | 4 |
| A | −4 | −9 | (−3, 2) | S | 1 | 2 |
| B | −4 | −9 | (−2, 3) | S | 1 | 2 |
| C | 0 | −4 | (1, 5) | A, B | 2 | 1 |
| D | 4 | 0 | (2, 6) | C | 2 | 1 |
| F | 4 | −4 | (−1, 7) | A, B | 2 | 1 |
| E | 9 | 4 | (4, 9) | D, F | 4 | 1 |
처음 귀걸이는 f[E] = 4개다(S-A-C-D-E, S-B-C-D-E, S-A-F-E, S-B-F-E).
- C를 빼면 4 − 2 × 1 = 2다.
- (8, 4, k = 4)를 더하면 u = 4라, 앞 점은 무리 0에서 x가 (4, 8)인 C다(f = 2). 뒤 점은 w = u_R − k_R = 4인 E다. E의 구간 (4, 9)가 8을 품어 g = 1이다. 4 + 2 × 1 = 6이다.
- S를 빼면 4 − 1 × 4 = 0이다.
7단계 · 복잡도와 흔한 실수
정렬과 이분 탐색이라 \(O(n \log n)\)이다. 점 10만 개와 변화 10만 개짜리 입력 둘(무작위 점, 10만 점이 한 사슬로 이어진 계단)을 합쳐 1초쯤 걸렸다.
- 점을 더할 때 S와 E를 새로 정한다. 둘은 처음 상태로 고정이다.
- 한 점을 지나는 사슬 수를 f + g로 센다. 앞의 방법 수와 뒤의 방법 수를 짝지으니 곱이다.
- g도 f처럼 “앞 무리의 구간 합”으로 구하려 한다. R → 뒤로 가는 조건에는 뒤 점의 k가 들어가서, 뒤 점들이 x 구간 하나로 모이지 않는다. 그래서 밀어 주기와 구간 품기로 바꿨다.
- 재귀로 경로 수를 세다 계단처럼 긴 사슬에서 재귀 한도에 걸린다.
-
프로그래머스 스쿨, “네오의 귀걸이” (https://school.programmers.co.kr/learn/courses/30/lessons/1842), 2026-10-01 조회. ↩