[백준 - Python] 27966. △

https://www.acmicpc.net/problem/27966

 

코드

N = int(input())

print((N-1) ** 2)
for i in range(2, N+1):
    print(1, i)

 

애드혹 문제란?

문제를 풀기 위해 잘 알려진 정교한 알고리즘을 적용하지 않고도 해결할 수 있는 유형의 문제!

 

굳이 유형 분류를 하자면, 구현, 그리디, 수학 유형으로 분류할 수 있다.

다시 말해, 정형화 된 방법론이 아니라, 창의적인 아이디어를 떠올려야 하는 문제

---

 

접근 방식

- 노드 사이 거리에 대한 설명이 없으면 1이라고 간주

- 모든 노드 쌍의 거리 합을 최소화하기 위해서는 하나의 노드에 다른 모든 노드가 연결된 형태여야 한다

- 가운데 노드를 1번 노드라고 한다면, 1번 노드와 나머지 (N-1)개 노드로 가는 거리 N-1에, 1번을 제외한 나머지 (N-1)개의 노드에서 1번을 제외한 나머지 (N-2)개의 노드로 가는 거리인 (N-1) * (N-2)

- (N-1) * 1 + (N-1) * (N-2) = (N-1) * (N-1) = (N-1) ** 2

 

배운 점

- 애드혹 문제 유형에 대해 알게 되었다.

- 여러 문제를 접해보는 것이 도움이 될 것 같다.