백준 15732 도토리 숨기기 Python 3

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

15732번: 도토리 숨기기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ15732.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def find_last_box(N, K, D, rules):
    left = 1
    right = N
    while left <= right:
        mid = (left+right)//2
        cnt = 0
        for start, end, step in rules:
            if start > mid: continue
            if mid > end:
                cnt += ((end-start)//step + 1)
            else:
                cnt += ((mid-start)//step + 1)
            if cnt >= D:
                right = mid-1
                answer = mid
                break
        else:
            left = mid+1
    return answer

input = sys.stdin.readline
N, K, D = map(int, input().split())
rules = list()
for _ in range(K):
    rules.append(list(map(int, input().split())))
print(find_last_box(N, K, D, rules))

---

풀이 과정

N개의 상자에 차례대로 도토리를 넣어 D개의 도토리를 숨긴다.

이때, 도토리를 숨기는 규칙이 K개 존재하고 각 규칙은 A, B, C로 이루어져 있다.

규칙은 A번 상자부터 B번 상자까지 C개의 상자 간격으로 도토리를 하나씩 넣는 것을 의미한다.

중요한 점은 모든 규칙을 적용하면서 맨 처음 상자에서 부터 도토리를 차례대로 넣으면서 마지막 도토리가 들어간 상자를 찾아야 한다는 점이다.

예제 1의 경우를 살펴보자.

N = 200, K = 2, D = 5, 규칙1: A = 100, B = 150, C = 10, 규칙2: A = 110, B = 150, C = 15

규칙 1, 2를 적용해서 상자에 넣을 수 있는 도토리의 개수는 다음과 같다.

100번 = 1개, 110번 = 2개, 120번 = 1개, 125번 = 1개, 130번 = 1개, 140번 = 2개, 150번 = 1개

따라서 규칙을 적용해서 도토리를 앞의 상자부터 차례대로 집어 넣으면 최종적으로 5번째인 마지막 도토리가 들어간 상자는 125번이다.

100번 = 1개, 110번 = 2개, 120번 = 1개, 125번 = 1개 -> D = 5개이므로

따라서, 마지막 도토리가 들어가는 상자의 번호는 125로 125가 정답이다.

 

이처럼 마지막 도토리가 들어가 있는 상자의 번호를 탐색해서 해당 상자까지 몇 개의 도토리가 담기느냐에 따라 정답을 찾아나갈 수 있다.

마지막 도토리가 담긴 상자의 번호는 1~N 중에 하나이므로 하나씩 순차적으로 탐색하는 선형 탐색을 해볼 수 있지만, 이분 탐색을 이용해서 시간복잡도를 줄여서 문제를 해결 할 수 있다.

 

• 이분탐색 적용하기

초기화 left = 1, right = N, mid = (left+right)//2

1. 탐색의 대상 mid를 마지막 도토리가 담긴 상자의 번호라고 가정한다. 

2. 해당 상자 mid까지 총 몇개의 도토리가 담겼는지 파악한다.

3. 해당 상자 mid까지 담긴 도토리의 개수 >= D이면, 해당 상자가 마지막 도토리가 담겨있을 가능성이 있으므로 answer를 갱신하고 5.로 간다.

4. 해당 상자 mid까지 담긴 도토리의 개수 < D이면, 해당 상자보다 뒤에 있는 상자에 마지막 도토리가 담겨있으므로 6.으로 간다.

5. right = mid - 1로 범위를 조정하고 다시 1.로 돌아간다.

6. left = mid + 1로 범위를 조정하고 다시 1.로 돌아간다.

위 과정을 left > right일 때까지 탐색하면 마지막 도토리가 담긴 상자인 answer을 최종적으로 구할 수 있다.

import sys
def find_last_box(N, K, D, rules):
	#탐색 범위 초기화
    left = 1
    right = N
    
    #이분 탐색
    while left <= right:
    	#mid번 상자를 마지막 도토리가 담긴 상자로 가정
        mid = (left+right)//2
        
        #mid번 상자까지 담긴 도토리의 수 카운트
        cnt = 0
        for start, end, step in rules:
        	#mid 이후의 상자에 적용되는 규칙이면 무시한다
            if start > mid: continue
            
            #규칙의 end가 mid 앞인 경우, 앞 상자들에 담긴 도토리 수를 카운팅
            if mid > end:
                cnt += ((end-start)//step + 1)
           	
            #규칙의 end가 mid보다 뒤인 경우, mid 상자까지 담긴 도토리 수를 카운팅
            else:
                cnt += ((mid-start)//step + 1)
                
            #mid번 상자까지 담긴 도토리 수가 D보다 크거나 같은 경우,
            if cnt >= D:
            	#더 앞쪽에 있는 상자에 마지막 도토리가 담길지 탐색하기 위해 right 범위를 줄인다
                right = mid-1
                #answer 갱신
                answer = mid
                break
                
        #mid번 상자까지 담긴 도토리 수가 D보다 작은 경우, 
        else:
        	#mid보다 뒤의 상자에 마지막 도토리가 담겨있으므로 left 범위를 늘린다
            left = mid+1
            
    return answer

input = sys.stdin.readline
N, K, D = map(int, input().split())
rules = list()
for _ in range(K):
    rules.append(list(map(int, input().split())))
print(find_last_box(N, K, D, rules))

#시간복잡도 = O(Klog N), 공간복잡도 = O(K)