취준/백준
[백준][Python][15970][구현] 화살표 그리기
puff
2020. 4. 12. 15:21
문제 : https://www.acmicpc.net/problem/15970
15970번: 화살표 그리기
직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다. <그림 1> 각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표
www.acmicpc.net
구현 문제다.
- 우선 입력을 정렬한다. 겹치는게 없으므로 정렬 조건은 설정 안해도 된다.
- 입력받은 좌표를 하나하나 돌아가면서
- 현재 좌표보다 왼쪽에 있는 것중에 색이 같은것을 찾는다.
- 현재 좌표보다 오른쪽에 있는 것중에 색이 같은것을 찾는다.
- 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)