백준 2212 - 파이썬

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

2212번: 센서

문제 풀이

이 문제는 처음에 문제 설명을 이해하는데 시간이 걸렸던거 같다. 결론적으로는 k개만큼 구간을 설정하여 수신 길이가 최소값이 되도록 하는 것이다.

 

처음에 떠올린 아이디어는 다음과 같다.

 

1. 입련된 센서들을 정렬한다.

2. 수신 길이는 n//k보다 작아야 한다.

3. 수신길이가 n//k보다 작은 것을 기준으로 구간 설정하면 된다

4. 수신 길이는 구간별 좌표의 처음과 맨 끝을 비교 (좌표가 하나일 때는 자기 자신과 비교)

 

결과만 먼저 얘기하면 위 풀이를 코드로 풀어내지 못했다. 수신길이를 정해놓고 수신길이에 맞게 구간을 설정하려고 하니 너무 복잡했고 구현도 하지 못했다. 1시간 정도 고민 끝에 다른 사람의 풀이를 참고하기로 하였다.(항상 참고하는듯.. ㅠ)

 

import sys

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

# 1 3 6 6 7 9
pos = sorted(list(map(int, sys.stdin.readline().split())))

if k >= n:
  print(0)
  sys.exit()

dist = []

for i in range(1, n):
  dist.append(pos[i] - pos[i-1])

dist.sort(reverse=True)

for _ in range(k-1):
  dist.pop(0)

print(sum(dist))

입력된 센서들의 좌표값을 정렬하는것은 나와 같았다. 이 사람은 센서들마다의 거리를 리스트에 내림차순으로 정렬한 후 k-1개의 값을 날렸다. 

 

센서들의 좌표값을 정렬하면 [1,3,6,6,7,9]가 되고, 센서들의 거리를 내림차순 정렬하면 [3,2,2,1,0]이 된다. 여기서 k-1개만 날리게 되면 3이 날라가게 되는데, 이는 연결고리를 끊는것과 같다.

출처: https://journeytosth.tistory.com/16

 

이 문제를 풀면서 느낀점은 처음에 아이디어를 생각해 낼때 너무 추상적으로 떠올리고 코드로 구현한다는 점이 아쉬운거 같다.

기본적으로 주어진 예제 입력을 활용하여 오름차순 정렬을 해보든 내림차순 정렬을 해보든 여러가지 방법을 시도 후 코드로 구현을 하고자 하면 좀더 나을거 같다는 생각이 들었다. 그리디는 역시 일단 뭐든 때려박아보면서 다 해보는게 중요한거 같다. 또한 사람의 방식으로 문제를 풀려고 하는 것이 아닌 컴퓨터의 방식으로 생각하고 풀어내는 것이 중요한거 같다. 이 문제에서는 각 센서들의 거리를 내림차순으로 정렬 후 k-1개의 값을 날리면서 연결고리를 끊는 것을 표현하였는데, 이처럼  컴퓨팅적 사고방식이 중요한거 같다.