백준 6236번 용돈 관리 JAVA

요구사항 정의

• N일 동안 사용할 금액이 주어지고, 통장에서 정확히 M번 돈을 인출 
• 한 번 인출할 때마다 K원을 뽑아 쓰며, 부족하거나 남아도 다시 인출 가능
• 정확히 M번 인출이 가능하도록 하는 최소의 K

제약 조건

• N ≤ 10^5
• 금액 ≤ 10^4

풀이 방법

시간복잡도를 신경안쓰고 푼다면 0부터 모든 금액의 합중에서 조건을 만족하는 가장 최소값을 구하는 것

 

for m : 0 .. sum(money):

   if(check(idx)) then answer = m

 

 

하지만 이렇게되면 시간복잡도가 O(10^9)가 되기때문에 시간초과가 발생함

 

그래서 떠올린게 이진탐색 

이진탐색에서는 2가지를 설계해야한다.

• 양쪽값의 범위
• true/false 조건

 

양쪽값의 범위

여기서 가장 최솟값은 사용할 금액의 최댓값이다.

100원씩 사용한다고 했을 때, 사용할 금액이 500원이면 절대로 사용못한다.

(무한 인출 반복)

 

여기서 가장 최댓값은 사용할 금액의 총합이다.

모든 금액의 합으로 시작하면 1번의 인출로 끝낼 수 있다.

 

여기서 문제에 따라서 Int의 범위를 넘어가는 경우도 있으므로 Long 쓸 수 있는지 판단하기

 

 

true/false 조건

여기서 true 조건은 인출 횟수가 M보다 작거나 같을 때(count <= M)이다.

처음에 왜 그런지 자꾸 헷갈렸는데 아래와 같은 문구가 있었다.

따라서 count < M도 가능하다는 것이다.

남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.

 

false 조건은 인출 횟수가 M보다 클 때이다.

 

코드