문제 보기 · Level 5 · 2017 카카오코드 본선 · 정답률 1% · 푼 사람 67명 (2026-09-30 기준)1
문제
삼각형 ABC 안에 핀 n개가 꽂혀 있다. 고무줄 세 개가 A–B, B–C, C–A에 묶여 있고, 이것을 삼각형 안쪽으로 밀어 핀에 걸면 새 도형이 생긴다. 각 고무줄은 끝점에서 끝점까지 핀을 꼭짓점으로 하는 꺾은선이 되고, 팽팽해서 안쪽으로 오목하다.
다음 두 조건을 모두 만족하는 도형의 수를 돌려준다.
- 두 고무줄이 서로 엇갈리지 않고, A, B, C 말고는 겹치지 않는다.
-
도형 안에 핀이 없다.
- 0 ≤ n ≤ 500, 좌표 절댓값 ≤ \(10^8\)
- 어떤 세 점도 한 직선 위에 있지 않다(삼각형 꼭짓점 포함)
풀이
막히면 한 단계씩 펼친다2. 고무줄과 삼각형 변 사이의 공간을 그 변의 주머니라 부른다.
필요한 개념
계산 기하 기초: 꼭짓점에서 본 핀들의 각도 순서를 외적으로 정한다. 그러면 도형을 세는 일이 세 꼭짓점의 “경계 순위” 세 개를 세는 일로 바뀐다. 그 경계를 빨리 세는 데 표를 차례로 채우는 동적 계획법과 누적 합을 쓴다.
셈의 기본 법칙: 도형 대신 경계 순위 세 개의 묶음을 세도 되는 것은 둘이 하나씩 짝이 맞기 때문이다(전단사 법칙).
행렬식: 외적 cross(o, p, q)는 p − o와 q − o를 두 열로 세운 2 × 2 행렬의 행렬식이다. 양수면 o에서 볼 때 q가 p보다 반시계 방향에 있다.
1단계 · 작은 예로 손으로 풀기
문제의 첫 예시다. A(0, 8), B(−4, 0), C(4, 0) 안에 D(−1, 3), E(1, 4)가 있다. 도형 안에 핀이 없으려면 D, E는 모두 어느 주머니 안이나 고무줄 위에 있어야 한다. 핀마다 주머니를 고르면 도형이 정해진다.
| 도형 | D의 주머니 | E의 주머니 |
|---|---|---|
| 사각형 AEBC | AB | AB |
| 오각형 ADBEC | AB | BC |
| 오각형 ADBCE | AB | CA |
| 오각형 ABDEC | BC | BC |
| 오각형 ABDCE | BC | CA |
| 사각형 ABCD | CA | CA |
3 × 3 = 9가지 중 (D, E)가 (BC, AB), (CA, AB), (CA, BC)인 셋은 두 고무줄이 엇갈려 안 된다. 답은 6이다. 사각형 ABCD에서 E는 고무줄 C → D → A가 감싼 주머니 안에 들어 있다. 핀이 꼭 고무줄 위에 있어야 하는 것은 아니다.
2단계 · 가장 단순한 방법과 그 속도
핀마다 주머니 셋 중 하나를 고르고, 주머니(볼록 껍질)를 그려 고무줄이 엇갈리는지 직접 본다. 고르는 방법이 \(3^n\)가지라 n = 500이면 어림없다. n = 10인 둘째 예시도 59,049가지를 그려야 한다.
3단계 · 핵심 아이디어
- 주머니는 볼록하다: 고무줄이 팽팽하니, 주머니 AB는 A, B와 AB에 고른 핀들을 감싸는 가장 작은 볼록 다각형이다. 그래서 핀마다 주머니만 고르면 고무줄 모양이 정해진다.
- 겹침은 꼭짓점에서만 보면 된다: 볼록 다각형은 한 꼭짓점에서 나가는 두 변 사이의 각 안에 통째로 들어간다. 주머니 AB는 A에서 변 AB와 “AB 핀 중 AB에서 가장 멀리 돈 핀” 사이의 각 안에 있고, 주머니 CA는 그 반대쪽 각 안에 있다. 그래서 두 주머니가 겹치지 않는 것은 “A에서 각도 순으로 볼 때 AB 핀이 모두 CA 핀보다 AB 쪽에 있다”와 같다. 각이 겹치면 A 근처에서 바로 겹친다.
- 조건 세 개: 각도 순위를 A에서 AB 쪽부터 α, B에서 BA 쪽부터 β, C에서 CB 쪽부터 γ로 매긴다. 그러면 조건은 (A) AB 핀의 α < CA 핀의 α, (B) AB 핀의 β < BC 핀의 β, (C) BC 핀의 γ < CA 핀의 γ 셋뿐이다. 순위는 외적의 부호로 비교해 정렬한다.
- 경계 셋으로 센다: a = AB 핀의 α 최댓값, b = AB 핀의 β 최댓값, c = BC 핀의 γ 최댓값으로 두자(없으면 0). (a, b, c)가 정해지면 핀이 갈 수 있는 주머니는 AB(α ≤ a, β ≤ b), BC(β > b, γ ≤ c), CA(α > a, γ > c) 중 많아야 하나다. 세 범위가 서로 겹치지 않기 때문이다. 그래서 도형 하나는 (a, b, c) 하나와 짝이 맞는다. 셀 것은 다음을 만족하는 (a, b, c)의 수다.
- 모든 핀이 갈 곳이 있다.
- a, b, c가 정말 최댓값이다. α 순위 a인 핀과 β 순위 b인 핀은 AB로, γ 순위 c인 핀은 BC로 가야 한다. a와 b는 함께 0이거나 함께 0이 아니다.
- 갈 곳 없는 핀 없애기: 핀이 갈 곳이 없는 경우는 (β ≤ b, α > a, γ ≤ c)이거나 (β > b, α ≤ a, γ > c)뿐이다. 그래서 (a, b)를 정하면 c는 L ≤ c ≤ R − 1이어야 한다. L은 “α ≤ a, β > b인 핀의 γ 최댓값”, R은 “α > a, β ≤ b인 핀의 γ 최솟값”이다. L과 R은 a, b를 한 칸씩 늘리며 앞 칸 값으로 채우는 표(동적 계획법)로 모두 \(O(n^2)\)에 구한다. 범위 안에서 c의 조건을 만족하는 개수는 b마다 만든 누적 합으로 바로 센다.
4단계 · 코드 흐름
- 외적 비교로 핀을 A, B, C 각각에서 각도 순으로 정렬해 α, β, γ 순위를 매긴다.
- 칸 (α, β)에 그 핀의 γ를 적은 표를 만들고, L[a][b]는 a를 늘리며 “β > b 쪽 최댓값”을, R[a][b]는 a를 줄이며 “β ≤ b 쪽 최솟값”을 채운다.
- b마다 “c = 0이거나 γ 순위 c인 핀의 β > b”의 누적 합을 만든다.
- (a, b)마다 경계 핀 조건을 보고, c 범위 [L, R − 1] 안의 개수를 더한다.
5단계 · 파이썬 코드
from functools import cmp_to_key
def cross(o, p, q):
return (p[0] - o[0]) * (q[1] - o[1]) - (p[1] - o[1]) * (q[0] - o[0])
def angle_rank(o, first, last, pins): # o에서 first 쪽부터 last 쪽으로 1, 2, …
turn = 1 if cross(o, first, last) > 0 else -1
order = sorted(range(len(pins)),
key=cmp_to_key(lambda i, j: -turn * (1 if cross(o, pins[i], pins[j]) > 0 else -1)))
rank = [0] * len(pins)
for r, i in enumerate(order, 1):
rank[i] = r
return rank
def solution(n, triangle, v):
A, B, C = map(tuple, triangle)
pins = [tuple(p) for p in v]
al = angle_rank(A, B, C, pins) # A: AB 핀이 CA 핀보다 먼저
be = angle_rank(B, A, C, pins) # B: AB 핀이 BC 핀보다 먼저
ga = angle_rank(C, B, A, pins) # C: BC 핀이 CA 핀보다 먼저
by_al, by_be, by_ga = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
for i in range(n):
by_al[al[i]], by_be[be[i]], by_ga[ga[i]] = i, i, i
grid = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n):
grid[al[i]][be[i]] = ga[i]
L = [[0] * (n + 1) for _ in range(n + 1)] # α ≤ a, β > b인 γ 최댓값
for a in range(1, n + 1):
row, prev, cur, best = grid[a], L[a - 1], L[a], 0
for b in range(n, -1, -1):
cur[b] = max(prev[b], best)
best = max(best, row[b])
R = [[n + 1] * (n + 1) for _ in range(n + 2)] # α > a, β ≤ b인 γ 최솟값
for a in range(n - 1, -1, -1):
row, nxt, cur, best = grid[a + 1], R[a + 1], R[a], n + 1
for b in range(n + 1):
if b >= 1 and row[b]:
best = min(best, row[b])
cur[b] = min(nxt[b], best)
okp = [] # c = 0 또는 γ 순위 c인 핀의 β > b
for b in range(n + 1):
pre = [1]
for c in range(1, n + 1):
pre.append(pre[-1] + (be[by_ga[c]] > b))
okp.append(pre)
total = 0
for a in range(n + 1):
for b in range(n + 1):
if (a == 0) != (b == 0):
continue
if a and (be[by_al[a]] > b or al[by_be[b]] > a):
continue # 경계 핀이 AB 주머니에 들지 못한다
lo, hi = L[a][b], R[a][b] - 1
if lo <= hi:
total += okp[b][hi] - (okp[b][lo - 1] if lo else 0)
return total
angle_rank: 핀은 모두 삼각형 안이라 한 꼭짓점에서 본 각이 180도보다 작은 범위에 있다. 그래서 외적 부호로 비교하는 정렬이 앞뒤가 맞는다.grid[al[i]][be[i]] = ga[i]: α 순위마다 핀이 하나라, 표의 한 줄에는 값이 하나뿐이다.okp[b][c]: c = 0(BC 핀 없음)은 늘 된다. c ≥ 1이면 γ 순위 c인 핀이 BC로 갈 수 있어야(β > b) 한다.
6단계 · 실행 추적
1단계의 예에서 D는 세 꼭짓점 모두에서 순위 1, E는 순위 2다. 경계 조건을 통과하는 (a, b)는 셋이다.
| (a, b) | AB에 든 핀 | c 범위 [L, R − 1] | 되는 c | 도형 |
|---|---|---|---|---|
| (0, 0) | 없음 | [0, 2] | 0, 1, 2 | ABCD, ABDCE, ABDEC |
| (1, 1) | D | [0, 2] | 0, 2 | ADBCE, ADBEC |
| (2, 2) | D, E | [0, 2] | 0 | AEBC |
(1, 1)에서 c = 1이 안 되는 까닭은, γ 순위 1인 D가 이미 AB에 들어 BC로 갈 수 없기 때문이다. (1, 2)나 (2, 1)은 경계 핀 조건에서 걸러진다. 합은 6이다.
7단계 · 복잡도와 흔한 실수
정렬이 \(O(n \log n)\), 표 채우기와 세기가 \(O(n^2)\)이다. n = 500이면 표가 25만 칸이고, 0.05초 안쪽에 끝났다.
- 모든 핀이 고무줄 위에 있어야 한다고 생각한다. 주머니 안에 들어 있기만 하면 된다(1단계의 사각형 ABCD).
- 고무줄이 곧은 경우(주머니가 빈 경우)를 빼먹는다. 예시 1의 여섯 도형은 모두 곧은 고무줄을 하나 이상 쓴다.
- 주머니끼리 겹치는지를 도형 전체에서 따지려고 한다. 볼록하니 세 꼭짓점의 각도 순서만 보면 된다.
- 각도를 atan2 실수로 비교한다. 좌표가 \(10^8\)이라 외적은 \(10^{16}\) 정도의 정수다. 파이썬 정수로 정확히 계산된다.