본문 바로가기

취준/백준

[백준][Python][15970][구현] 화살표 그리기

문제 : https://www.acmicpc.net/problem/15970

 

15970번: 화살표 그리기

직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다. <그림 1> 각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표

www.acmicpc.net

구현 문제다.

 

  1. 우선 입력을 정렬한다. 겹치는게 없으므로 정렬 조건은 설정 안해도 된다.
  2. 입력받은 좌표를 하나하나 돌아가면서
    1. 현재 좌표보다 왼쪽에 있는 것중에 색이 같은것을 찾는다.
    2. 현재 좌표보다 오른쪽에 있는 것중에 색이 같은것을 찾는다.
  3. tmpret에 왼쪽, 오른쪽 값이 나오는데 그 중에서 작은것을 골라 답에 더해준다

 

import sys

n = int(sys.stdin.readline())

d = []
for _ in range(n):
    d.append([int(i) for i in sys.stdin.readline().split()])


d.sort()
ret = 0

for i in range(n):
    tmploc, tmpclr = d[i]
    tmp = i-1
    tmpret = [9912341234, 9912341234]
    # left
    while tmp >= 0:
        if d[tmp][1] == tmpclr:
            tmpret[0] = abs(tmploc - d[tmp][0])
            break
        else:
            tmp -= 1

    # right

    tmp = i+1
    while tmp < n:
        if d[tmp][1] == tmpclr:
            tmpret[1] = abs(tmploc - d[tmp][0])
            break
        else:
            tmp += 1
    ret += min(tmpret)


print(ret)