얼마를 인출 했을 때 N일 동안 사용할 금액을 충족하면서 가장 적은 금액(k)이 되는지를 결정하는 문제
- n, m : n일 동안 m번 인출
- n일 동안 사용 할 금액
- 입력을 받는다.
- 반활한 최소 인출금액 변수를 선언한다.
- 최소 인출 금액(left)과 최대 인출 금액(right)를 정의한다.
- left <= right 인동안 이분 탐색을 수행한다.
- 중간값을 구한다.
- 중간값을 인출 했을 때 n일동안 사용 할 금액을 충족하는지 확인한다.
- 충족하면 최소 인출금액 변수를 갱신하고 더 최소금액이 있는지를 확인하기 위해서 최대 인출 금액을 갱신한다.
- 충족하지 않으면 최소 인출 금액을 갱신한다.
- 최소 인출 금액 변수를 반환한다.
- 인출한 금액보다 사용할 금액이 크면 false를 반환해서 인출한 금액을 늘려야한다.
- (left) 최소값을 인출할 금액 중 최대값으로 하면 이 로직이 필요 없다. 속도 차이는 없었다.
지문이 이해가 되지 않아서 풀어서 다음과 같이 풀어서 이해했다.
현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.
- 지문이해1
오늘 은행에서 k원을 인출해서 쓴 금액 보다 쓰고 남은 금액이 크면 남은 금액을 지갑에 보관합니다. 다음 날 사용 할 금액이 지갑에 있는 돈보다 작거나 같으면 은행에서 인출하지 않고 지갑에 있는 돈을 사용합니다. 반대로 인출해서 쓸 돈이 쓰고 남은 금액보다 크면 은행에 다시 입금하고 다음 날 은행에서 k원을 새로 인출 합니다.
- 지문이해2
인출 금액이 1000원이고 사용할 금액이 300원이면 700원이 남으니까 700원을 지갑에 넣어뒀다가 다음날 사용 할 금액이 700원 보다 작거나 같으면 은행에서 인출하지 않고 지갑에 넣어둔 700원으로 해결 합니다. 1000원을 인출 하고 700원을 사용했으면 300원밖에 안남으니 은행에 다시 입금하고 다음날 1000원을 새로 인출합니다