(JAVA) 백준 6236번 : 용돈 관리

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

6236번: 용돈 관리

 

이진 탐색 문제이다.

 

한글 번역이 헷갈리게 되어있어 문제 풀이 또한 헷갈렸었다..ㅠㅠ

 

하지만 타 문제에 비해 어렵진 않았던 문제.

 

 

 

핵심

---

 

  -  돈이 남아도 횟수(M) 를 채우기 위해 넣고 빼기 가능.

 

        -> 이 말은 즉슨, M번 이하만 채워도 M번과 동일하게 임의로 넣고빼면서 맞출 수 있다.

        -> M번 이하인 인출 비용 중 최솟값 구하기.

 

 

  -  정렬된 배열 : 인출 금액 (1원 ~ 최대 사용 금액 * M 원)

 

 

  -  계산 : For문으로 각 사용금액을 탐색함.

 

        ->  현재 잔액 < 지출 금액 인 경우, 현재 잔액을 전부 반납하고 인출

        *** 여기서 필자도 헷갈렸다.(번역...) 즉, 이런 경우에 현재 잔액을 전부 버리고 인출한 금액만 가지고 계산을 한다는 것이다.

        ->  현재 잔액 > 지출 금액 인 경우, 인출하지 않고 현재 잔액 - 지출 금액 진행.

 

 

  ex) 100원 남고, 지출이 400원일 때. K(인출금액) = 500 이라면

 

    1) 100원을 버린다 : 현재 0원

    2) K(500)원을 인출한다 : 현재 500원

    3) 400원을 지출한다 : 현재 100원

    4) 현재 금액을 가지고 다음 지출로 넘어간다.

 

 

  -  그렇게 모든 인출 금액을 탐색한 후

 

        -> 인출 횟수 > M : 윗 배열 탐색. (low = mid + 1)

        -> 인출 횟수 <= M : 아랫 배열 탐색. (high = mid - 1)

        *** 탐색 시 예상 인출 금액(mid) < 지출 금액 인 경우도 따져봐야 함. 만약, 500원 인출에 1000원 지출이 있으면 이 문제가 성립하지 않기 때문에 빠르게 종료하여 다른 mid로 진행한다.

 

 

 

 

이 핵심들만 기억하면 바로 해결 할 수 있다.

 

그래서 별도 매커니즘을 작성하지 않겠다.

 

이해가 되지 않는 부분은 소스코드를 참고하길 바랍니다.

 

 

 

감사합니다!

 

소스코드

---