문제링크
감상평
- 진짜 너무너무너무너무너무너무 어려워서 머리가 터질뻔 했다
- 문제 이해하는 것도 어려워가지고 특히 연속된 호 찾는게 뭔 소리인가 해서 어지러웠다
스포일러 주의
처음 예제를 보고 "연속된 호로 만든 영역의 (넓이 × 미분가능한 조각 수)가 그 안의 숫자와 같아야 한다"는 규칙을 이해하는 것부터 한 고비였다.
근데 진짜 시간 낭비는 그 다음이었다. 처음 4시간 동안 "한 region에는 label이 하나만 들어간다" 고 잘못 이해하고 풀었다. 같은 score의 label이 같은 region에 묶일 수 있다는 걸 나중에야 깨달았다. 게다가 초기엔 [넓이 × smooth piece 수] 제약 자체를 무시하고 무작정 영역을 나눴는데, 다시 문제를 읽어보니 이것도 틀린 접근이었다. 다음날 6시간 더 투자해서 결국 풀었다.
처음 구한 것:
그래서 생각해보니 각각의 숫자는 각각의 의미를 가진다. (영역의 넓이 × 미분 가능한 둘레 조각 수):
- 21 → (3, 7)
- 27 → (3, 9)
- 15 → (3, 5)
- 25 → (5, 5)
- 9 → (3, 3)
- 63 → (7, 9)
- 35 → (7, 5)
- 45 → (9, 5)
- 288 → (16, 18), (12, 24), (9, 32) 중 하나
그래서 일단 가장 만만해 보였던게 9였다. 9는 무조건 나올 수 있는 모양이 정해져있다. (가장 왼쪽 하단을 (1, 1)이라 하면) (1, 3)에 있는 9가 되는 모양이 1개 밖에 없다고 생각했고, (9, 5)와 (9, 7)도 같은 영역 안에 집어넣어야지 되기 때문에 고정되어 있다고 생각했다. 그리고 (1, 8)와 (3, 9)에 있는 21도 영역상 겹칠 가능성이 높다고 생각했다. (2, 2)와 (4, 3)에 있는 63도 당연히 그럴 거라 생각했다.
대략적으로 구역을 나눴다. 나누고 나서 계산해보니 63, 35, 288의 계산이 맞지 않아서 다시 나눠줬다. 나머지 구역들의 합이 49가 나왔고, 63, 35, 288의 구역 넓이 합이 32가 되면 되는데 후보를 보니 {7, 7, 18}, {9, 7, 16}, {9, 5, 18}이 있었다. 아무리 63의 넓이를 넓히려 해도 숫자가 맞지 않아서 7로 고정, 35도 7로 고정, 288도 18로 고정했다. 나중에 보니 호의 꺾임이 맞지 않아서 바꿀 수 있는 부분만 바꿔서 답을 맞췄다.
숫자를 채우고 계산은 귀찮아서 프로그래밍 돌림:
grid = [
[21, 21, 21, 27, 27, 288, 288, 15, 25],
[21, 21, 21, 27, 27, 15, 15, 25, 25],
[21, 27, 27, 288, 288, 15, 15, 25, 9],
[25, 27, 27, 288, 288, 45, 45, 25, 9],
[25, 25, 25, 27, 288, 45, 45, 45, 9],
[288, 25, 288, 63, 288, 288, 288, 45, 45],
[9, 9, 63, 63, 288, 35, 35, 45, 45],
[9, 63, 63, 288, 9, 9, 35, 288, 288],
[63, 63, 288, 288, 9, 35, 35, 35, 35],
]
row_sums = [sum(row) for row in grid]
col_sums = [sum(grid[i][j] for i in range(9)) for j in range(9)]
row_sq = sum(r * r for r in row_sums)
col_sq = sum(c * c for c in col_sums)
ans = row_sq + col_sq
print(f"답: {ans:,}")
최종답
답: 13,682,882
