문제 링크
https://www.acmicpc.net/problem/15732
🕒 Python 풀이시간: 40분
def binary_search(rules,target,start,end):
while start<=end:
mid=(start+end)//2
cnt=0
for i in range(k):
a,b,c=rules[i]
if mid<a:
continue
elif mid>b:
cnt+=(b-a)//c+1
else:
cnt+=(mid-a)//c+1
if cnt<target:
start=mid+1
else:
answer=mid
end=mid-1
return answer
n,k,d=map(int,input().split())
rules=[]
start=1000000
end=0
for _ in range(k):
a,b,c=map(int,input().split())
start=min(a,start)
end=max(b,end)
rules.append((a,b,c))
print(binary_search(rules,d,start,end))다람쥐의 도토리 숨기기 문제! 🐿️🌰
다람쥐가 도토리를 숨길 때, K개의 규칙에 따라서 앞에서부터 숨기는데 이 때, D개의 도토리의 마지막 도토리를 어디다가 숨겼는지를 찾는 문제이다. 이분탐색의 대표적 유형인 Parametic Search라고 할 수 있다.
먼저 예제를 파헤쳐보자. 상자를 규칙에 따라 나열하고 우리는 D번째 도토리만 찾으면 되므로 현재의 상자 위치에서 도토리가 앞쪽에 몇개 있는지만 구하면 된다. 즉 for문을 통해서 각 이분탐색을 수행할 때, K개의 규칙을 O(K) 하면서 상자의 개수의 1,000,000만 수행하면 된다. 이러면 시간복잡도 내로도 가능하며 역으로 시간복잡도를 가지고 이진탐색임을 확인할 수 도 있다.
K를 for문을 통해 불러오기 위해 리스트에 넣어놓고 각 이분탐색을 수행한다. 우리는 각 규칙에서의 a값의 최소와 b값의 최대 사이만 찾아보면 되기 때문에, 즉 상자가 존재할 수 있는 구간만 찾아보면 되기 때문에 start,end를 이 값으로 설정해놓고 목표는 우리가 구해야 하는 D번째 도토리로 둔다.
이제 이진탐색을 수행한다. 각 규칙을 불러오면서 각 규칙에 따라 현재 지점까지의 도토리를 전부 채워넣었을 경우의 도토리 수를 구하는 것이다. 규칙의 a보다 현재 지점이 작으면 도토리가 0개이므로 continue하고 b보다 현재 지점이 크면 규칙 내에서만 도토리의 수를 구한다. 또한 범위내에 현재 지점이 있다면 시작지점~현재지점까지의 도토리의 수를 구해서 더해주면 된다. 이렇게 되면 규칙에 따라 꽉 채워넣었을 때의 도토리의 수가 나오게 되고 이제 이분 탐색을 수행하면 된다.
도토리가 목표인 D보다 적다면 범위를 늘려준다. 도토리가 목표인 D보다 크다면 우리가 찾는 D번째가 포함되었을 수도 있지만 더 작은 범위의 탐색이 가능하다. 이런식으로 탐색을 수행하면 정답이 도출된다.
이렇게 Python으로 백준의 "도토리 숨기기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
