[BOJ] 백준 15975번 Python

백준 15975번 Python

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

 

문제

---

직선 위에 직선 위에 N개의 점들이 주어지고 각 점은 N개의 색깔 중 하나를 가진다.

편의상, 색깔은 1부터 N까지의 수로 표시하고, 점들의 좌표는 모두 다르다.

각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다.

여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다.

만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.

각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표 ℓ_p를 그린다.

특별히 점 p에 대해서 수평선 상에 같은 색깔의 다른 점이 없다면 |ℓ_p| = 0이다.

여기서 |ℓ_p|는 화살표 ℓ_p의 길이를 나타낸다.

예를 들어, 점들을 순서쌍 (좌표, 색깔)로 표시할 때, p₁ = (0, 1), p₂ = (1, 2), p₃ = (3, 1), p₄ = (4, 1)라고 하자.

점 p₁의 화살표 |ℓ_p1|는 p₁ → p₃로 연결된다.

점 p₃와 p₄의 화살표 |ℓ_p3|, |ℓ_p4|는 각각 p₃ → p₄와 p₄ → p₃로 연결된다.

점 p₂의 경우는 같은 색깔의 다른 점이 존재하지 않는다.

따라서 모든 화살표들의 길이의 합은 |ℓ_p1| + |ℓ_p2| + |ℓ_p3| + |ℓ_p4| = 3 + 0 + 1 + 1 = 5이다.

점들의 좌표와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이의 합, 다시 말해서, Σ_p |ℓ_p| 을 출력하는 프로그램을 작성하시오.

 

 

입력

---

표준 입력으로 다음 정보가 주어진다.

첫 번째 줄에는 점들의 개수를 나타내는 정수 N이 주어진다.

다음 N개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x와 y가 주어진다.

 

 

출력

---

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

 

 

제한 및 서브태스크

---

제한
모든 서브태스크에서 점들의 좌표 x와 색깔 y는 각각 0 ≤ x ≤ 10⁹, 1 ≤ y ≤ N을 만족한다.

서브태스크 1

점들의 색깔은 모두 동일하고 점들의 개수는 1 < N ≤ 10을 만족한다.

서브태스크 2
점들의 색깔은 정확히 두 가지이고 점들의 개수는 1 ≤ N ≤ 2,000를 만족한다.

서브태스크 3
점들의 개수는 1 ≤ N ≤ 10,000를 만족한다.

서브태스크 4
점들의 개수는 1 ≤ N ≤ 100,000를 만족한다.

반응형

풀이

---

import sys
input = sys.stdin.readline


N = int(input().rstrip())

graph = dict()
for _ in range(N):
    pos, clr = map(int, input().rstrip().split())
    if clr not in graph:
        graph[clr] = list()
    graph[clr].append(pos)


ans = 0
for cur in graph:
    li = sorted(graph[cur])

    if len(li) == 1:
        continue

    tmp_list = list()
    for i in range(len(li)-1):
        tmp_list.append(li[i+1]-li[i])

    ans += tmp_list[0]
    ans += tmp_list[-1]

    for j in range(len(tmp_list)-1):
        if tmp_list[j] < tmp_list[j+1]:
            ans += tmp_list[j]
        else:
            ans += tmp_list[j+1]

print(ans)

 

728x90

다소 난해해 보이는 문제이다.

 

일단 문제를 간단하게 정리하여 보자.

 

다수의 색깔이 있고, 색깔별로 점들이 찍혀있다.

 

특정 색깔에 점의 개수가 하나 이하라면 점 사이의 거리를 측정할 수 없기 때문에 무시하여도 된다.

 

임의의 색깔에 한 개 이상의 점이 존재할 때 각 점에서 가장 가까운 점과의 거리를 구한다.

 

이를 총합하여 출력하면 된다.

---

 

문제를 풀기 앞서 문제 풀이 아이디어를 공유해 보겠다.

 

일단 딕셔너리의 key값을 색깔로 value 값을 점들의 좌표로 받아 저장해 준다.

 

이후 각 색깔별로 점들 사이의 거리를 측정하여 이를 임의의 리스트에 저장한다.

 

임의의 리스트에는 각 점들 사이의 거리가 담기게 되는데 이때 더 가까운 거리

 

즉, 더 작은 값을 채택하여 ans 변수에 담는다.

---

graph = dict()
for _ in range(N):
    pos, clr = map(int, input().rstrip().split())
    if clr not in graph:
        graph[clr] = list()
    graph[clr].append(pos)

 

입력값을 풀이에 맞게 재단하는 과정이다.

 

from collections import defaultdict

 

조금 더 편하게 풀고 싶다면 defaultdict 모듈을 사용해도 된다.

 

(필자는 사용하지 않았다.)

 

for cur in graph:
    li = sorted(graph[cur])

    if len(li) == 1:
        continue

 

각 색깔별로 풀이를 반복한다.

 

이후 가장 가까운 점 사이의 거리를 구하기 위해 sort 해주었다.

 

길이가 1인 key값의 value는 점사이의 거리를 측정할 수 없기 때문에 continue 한다.

 

tmp_list = list()
for i in range(len(li)-1):
	tmp_list.append(li[i+1]-li[i])

 

점 사이의 거리를 임의의 리스트에 저장한다.

 

ans += tmp_list[0]
ans += tmp_list[-1]

for j in range(len(tmp_list)-1):
    if tmp_list[j] < tmp_list[j+1]:
        ans += tmp_list[j]
    else:
        ans += tmp_list[j+1]

 

처음의 점과 마지막 점에서 가장 가까운 점은 항상 하나이기 때문에 미리 ans 변수에 더한다.

 

이후 수직선을 기준으로 좌우 점 중 거리가 더 가까운 점과의 거리를 ans 변수에 더한다.

---

다소 난해한 풀이라고 느껴질 수 있다.

 

하지만 각 점 사이의 거리를 저장해 두고 더 짧은 거리를 채택하여 ans변수에 더한다 라는 대전제를 이해하고 풀이를 보면 이해하기 쉬울 것 같다.