백준 1654번 문제(랜선 자르기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

1654번: 랜선 자르기

 

정답 코드는 아래와 같습니다.

import sys
 
def calc(start, end, arr, n):
  if end - start <= 1:
    return start
  mid = (start + end) // 2
  rst = 0
  for item in arr:
    rst += (item // mid)
  if rst < n:
    return calc(start, mid, arr, n)
  else: # rst >= n
    return calc(mid, end, arr, n)
 
def solve():
  k, n = map(int, sys.stdin.readline().rstrip().split())
  arr = []
  big = 0
  for _ in range(k):
    x = int(sys.stdin.readline().rstrip())
    big = max(big, x)
    arr.append(x)
  print(calc(1, big+1, arr, n))
 
solve()
 

 

제가 문제를 푸는 방식은 거의 항상 동일합니다.

그래야만 어떤 유형의 문제라도 일관성 있게 풀어낼 수 있기 때문입니다.

 

가장 단순한 풀이를 먼저 떠올립니다.

여기서는 길이가 1인 경우부터 계속 키워나가다 보면, 랜선의 갯수가 n 을 초과하는 때가 있겠죠.

그리고 그 때 바로 이전 값이 정답이 될 것임을 충분히 생각해낼 수 있습니다.

주어진 예시에서는 길이가 200인 경우 갯수가 11개가 되고, 201인 경우 갯수가 11개를 초과하므로 200이 정답이라고 할 수 있겠습니다.

 

그 다음으로 해야 할 것은 이 풀이가 시간 안에 풀리는가를 확인하는 것입니다.

가능한 숫자는 2의 31제곱이므로 2의 10제곱을 1,000 정도로 잡으면, 빠르게 0이 9개임을 계산할 수 있습니다.

즉, 10억이 넘는다는 것이죠.

게다가 각 경우에 대하여 K번의 나눗셈을 진행해야 하므로(길이로 나누어 갯수를 구하는 연산) 10억 * 10,000(K의 최댓값) 만큼(10조번)의 연산이 필요하고, 이러한 방식으로는 시간 안에 문제가 풀리지 않는다는 것을 알 수 있습니다.

 

그 다음으로 해야 할 것은 효율적인 풀이를 생각해내는 것인데, 이 부분이 항상 어렵습니다.

풀이가 바로 떠오른다면 아주 훌륭합니다.(풀이가 바로 떠오르는 분이라면 지금 이 글을 읽지도 않을 것입니다)

보통은 생각이 잘 나지 않기 마련인데, 이 경우 여러가지 방식을 통하여 풀이를 떠올릴 수 있도록 돕습니다.

 

728x90

 

제가 가장 자주 사용하는 방법은 작은 경우부터 직접 해보는 것입니다.

1인 경우, 2인 경우, 이런 식으로 말이죠.

이 문제도 길이가 1인 경우, 2인 경우를 해보면, 그 다음에 3인 경우에 대하여 확인하려는 사람은 없을 것입니다.

왜냐하면 3인 경우에도 길이가 충분히 작아서 굳이 계산해보지 않아도 11을 훨씬 넘는 다는 것을 직관적으로 알 수 있기 때문입니다.

따라서 3, 4, 5, 6.. 이런 숫자들을 모두 넘기고 50 정도를 넣어 볼 것입니다.

여기서, 이것이 우리가 도서관에서 책을 찾는 방식과 동일하다는 것과 그것이 근본적으로는 binary search(이분 탐색)의 variation 이라는 것을 알 수 있어야 합니다.

만일 이분 탐색을 공부하지 않았거나, 공부하였어도 피상적으로 공부했다면 떠오르지 않을 것입니다.

 

그 다음으로는 새로운 방식으로는 시간 안에 계산할 수 있는지를 확인해보고, 가능하다면 풀이를 작성하면 됩니다.

log(2^31) * 10,000 => 약 30만, 시간 안에 충분히 계산 가능

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=8YZHSZdkopc 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)