[백준/15732] 도토리 숨기기 (Python)

Problem : https://www.acmicpc.net/problem/15732

15732번: 도토리 숨기기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:10:28

 

---

 

문제 설명

 

 

HEPC 1등 상금으로 도토리 D개를 받은 욕심많은 다람쥐 수형이는 자신의 모든 도토리를 뺏기지 않게 보관하려고 한다. 수형이는 1부터 N까지의 번호가 붙여있는 N개의 상자를 가지고 있고 이 안에 도토리를 넣어 다른 다람쥐들이 찾지 못하게 전부 숨기려고 한다. 상자가 너무 많아 도토리가 있는 상자를 모두 외울 수 없는 수형이는 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 더 넣는 규칙을 만들었다! 다른 다람쥐들이 규칙을 눈치채고 모든 도토리를 잃는 것이 무서운 나머지 이러한 규칙들을 K개를 만들어 도토리를 최대한 안전하게 저장해 놓으려고 한다. 예를 들어 100번 상자부터 150번상자까지 10개 간격으로, 110번 상자부터 150번 상자까지 15개 간격으로 넣는다면 100, 110, 120, 125, 130, 140, 150번 상자에 도토리가 있으며 110번 상자와 140번 상자에는 2개의 도토리가 들어가 있게 된다. 상자 하나에 들어갈 수 있는 도토리의 개수는 제한이 없으며 앞의 상자부터 최대한 꽉꽉 채워나간다고 했을 때 마지막 도토리가 들어가 있는 상자의 번호를 출력하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 B번 상자까지 C개 간격으로 도토리를 하나씩 넣는 규칙을 뜻한다. D는 모든 규칙으로 넣을 수 있는 도토리의 수보다 같거나 작다.

 

출력

 

D개의 도토리를 규칙에 맞게 상자 앞에서부터 넣었을 때 마지막 도토리가 들어가는 상자의 번호를 출력하시오.

 

입력 예시

 

200 2 5
100 150 10
110 150 15

 

출력 예시

 

125

 

 

---

 

풀이

 

단순히 모든 도토리 개수를 구하는 경우는 시간이 매우 오래 소요될 것이다. 가능한 경우의 최악의 수를 상정하면, N*K(모든 도토리가 1부터 N까지 1개 간격으로 주어질 경우)개의 숫자를 처리해야 한다.

 

관점을 바꾸어 보자. 우리가 어떤 상자 숫자를 임의로(T) 정하고, 모든 규칙에 대해 이 상자까지 도토리가 얼마나 보관되는지 계산해 볼 수 있겠다. 시작 지점, 끝 지점, 간격을 A, B, C라고 두자.

 

• T < A인 경우 이 규칙은 우리가 정한 상자 숫자 밖에 위치하므로 pass.
• A <= T <= B 인 경우 우리는 [A, T]구간 내의 도토리 숫자를 세면 된다.
• B < T인 경우 이 구간 내의 모든 도토리가 포함된다.
  • 즉 두 조건을 합쳐 [A, min(B, T)] 구간 내의 도토리 개수를 구하면 된다. 그 값은 (min(B, T) - A) // C + 1이 될 것이다.

즉 임의의 상자 숫자에 대해 O(K) 시간복잡도 내에 모든 도토리 개수를 구할 수 있다. 이 도토리 개수가 D개인 상자 숫자 중 가장 작은 값을 찾는 문제로 변화한다.

도토리 개수가 D개를 찾는 문제라면, 우리는 또한 이분 탐색을 생각해볼 수 있다. 상자는 총 N개이고, 이분 탐색으로 조건을 만족하는 (lower bound) 상자를 찾으려면 O(logN) 시간복잡도가 걸림을 알 수 있다. 즉 총 시간복잡도 O(KlogN)내에 우리가 원하는 값을 찾아낼 수 있다!

 

풀이 코드

import sys
input = sys.stdin.readline

N, K, D = map(int, input().split())
rules = [list(map(int, input().split())) for _ in range(K)]

def check_rules(target) :
  res = 0
  for a, b, c in rules :
    if target < a :
      continue
    b = min(b, target)
    res += (b - a) // c + 1
  return res >= D

def binary_search() :
  start, end = 0, N
  while start < end :
    mid = (start + end) // 2
    if check_rules(mid) :
      end = mid
    else :
      start = mid + 1
  return end

print(binary_search())

풀이 완료!