[BOJ 6236] 용돈관리

리뷰

• 사이사이 생략된 말들이 조금 있어서 문제 해석이 굉장히 어려웠던 문제이다.
• 남은 금액: 인출한 금액 - 하루사용금액

하루사용 금액		100	400	300	100	500	101	400
남은금액	500(인출)	400	0	500(인출) -> 200	100	500(인출) -> 0	500(인출) -> 399	500(인출) -> 100
총인출횟수	1	1	1	2	2	3	4	5

• 조건A: "남은 금액이 그날 사용할 금액보다 많아도 다시 인출가능하다"
  조건A로 의해, 인출금액이 x일 때 총 인출 횟수가 M이하이면 결국 정확히 M번 인출해야하는 조건을 성립하게 된다.
  
  인출금액의 범위: [하루 사용할 금액들의 max값 ~ 하루 사용할 금액들의 sum값] 이기 때문이다.
  max값부터 시작하는이유: 인출금액이 max값보다 적다면, 사용할 금액 max값인 하루를 애초에 보낼 수가 없다.
  
  ※ max값부터 시작하기에 결국 모든 날은 조건 A를 만족한다. 즉, 인출횟수가 M번 이하인 경우는 조건A에 의해 사실상 M번 인출 가능한 꼴이다.

 

시간복잡도

위의 해석한 사실들을 파악했으니, 문제분석을 해보자.

• N일: (1 ~ 100,000)
• 인출해야하는 횟수 M: (1 ~ N)
• 하루사용금액 i: (1 ~ 10,000)
• 가능한 시간복잡도: O(log(N) * N),  O(log(M) * N),  O(log(i) * N)

 

유형

Goal: 정확히 M번 인출할 수 있는 최소 인출금액 K

 

결국, 인출금액을 묻는 문제이다.

1. 완전탐색: 인출금액 1원부터 브루트포스하게 M번 인출 가능여부를 확인한다면, O(금액범위 * N)으로 금액범위가 10,000만 되어도 시간복잡도를 초과하게 된다. -> 불가
2. 그럼 인출금액을 찾는 과정에 대한 시간복잡도를 log scale로 줄이면 가능성이 보인다.
3. Input Size가 크고,
4. log scale을 고려해야하고,
5. 최소 or 최대를 묻는 문제라면,
6. 파라매트릭 서치를 의심해보자.

파라매트릭 서치가 가능한지 판단하려면 문제 해석을 통해, "조건을 만족하는 경우 (True인 영역), 조건을 만족하지 않는 경우(False인 영역)"이 [T T T T T T T T F F F F F F F] 와 같이 영역이 완전히 분리되어야 한다.

 

인출금액 K가 x일 때, 

조건을 만족하는 경우를 생각해보자.

• M번 인출 이하(서두에서 해석을 바탕으로 도출한 결과)라면 조건A에 의해 이상인 금액들은 모두 M번 인출해야하는 조건을 만족한다.
• 즉, [ 탐 색 후 보 군, 인출금액x, T  R  U  E]

조건을 만족하지 않는 경우를 생각해보자.

• M번 인출 초과라면 x 이하인 금액은 무조건 인출횟수가 더 커질 수 밖에 없으므로, M번 인출해야하는 조건을 만족하지 않는다.
• 즉, [ F A L S E, 인출금액x, 탐 색 후 보 군]

 

[T T T T T T T F F F F F F F] 형태이므로, 파라매트릭 서치가 가능하다.

 

 

파라매트릭 서치 설계

1. 인출금액 탐색범위 설정: [하루 사용할 금액들의 max값 ~ 하루 사용할 금액들의 sum값]
   max값인 이유는 위에서 설명하였다.
   하루사용할 금액 범위의 최대치인 10,000이 아니라 sum값인 이유는 다음과 같다.
   만약 인출금액이 10,000일 때 인출횟수 M을 초과해버릴 수 있다.
   ex) M=1, 하루사용할 금액[10000, 10000] -> 실제 인출횟수: 2
   
   
2. 탐색 설정
   조건을 만족하는 경우: 인출횟수구하기(par: 인출금액) <= outLimit이면 조건 A에 의해 이상인 금액은 무조건 만족한다.
    [ 탐 색 후 보 군, 인출금액(mid), T R U E]
    -> result = mid, right = mid - 1
   주의: right = mid로 두면, 무한루프에 빠질 수 있으므로, 정답후보인 mid를 result에 기록해두고 right = mid -1로 설정
      
    
   조건을 만족하지 않는 경우: 인출횟수구하기(par: 인출금액) > outLimit이면 이하인 금액은 무조건 인출횟수가 더 커지는 꼴이므로 만족하지 않는다.
    [ F A L S E, 인출금액(mid), 탐 색 후 보 군]
    -> left = mid + 1