[C++, python] 백준 6236번 풀이 ( 용돈 관리 )

정민경·2024년 2월 2일
0

baekjoon

목록 보기
56/57
post-thumbnail

- 문제 ( 6236번 ) : 용돈 관리

  • 며칠동안 용돈을 사용할건지 ( N ), 통장에서 인출을 몇번할건지에 ( M ) 대한 정보를 입력받으면 통장에서 돈을 한번 인출 시 얼마를 인출해야 정확하게 N일동안 M번 인출할 수 있는지 구하는 프로그램 작성.
    • 현재 가지고 있는 금액으로 하루를 생활하지 못하면 남은 금액을 통장에 집어넣고 다시 인출해 사용.
    • 정확히 M 번을 맞추기 위해 현재 가지고 있는 금액으로 하루를 생활할 수 있더라도 남은 금액을 통장에 넣고 다시 인출할 수 있다.

- 입력 및 출력

[ 입력 ]

  • 첫번째 줄에 현우가 사용할 총 요일 ( N ) 과 인출 횟수 ( M ) 이 공백을 사이에 두고 입력.
    ( 1 ≤ N ≤ 100,000 , 1 ≤ M ≤ N )
  • 두번째 줄부터 총 N 개의 줄에 걸쳐 현우가 i 번째 날에 이용할 금액 입력.
    ( 1 ≤ 금액 ≤ 10,000 )

[ 출력 ]

  • 첫 번째 줄에 현우가 통장에서 인출해야 할 최소금액 ( K ) 출력.

- 문제 풀이

  • 이번 문제는 조건에 맞는 인출 금액 중 최소금액을 구하는 문제이다.
    즉, 최소금액과 최대금액 사이에서 조건을 만족하는 금액을 찾아야 하는 문제이다.
    naïve 하게 생각하면 최소금액인 1 부터 최대금액인 ( ∑ 입력받은 값 ) 까지 1씩 증가시켜가며 탐색하면 해결되는 문제지만, 시간초과가 발생하게 된다.

    따라서 이번 문제는 이진탐색 ( binary search ) 방법으로 해결하면 된다!

  • 이진탐색 시 left, right 범위를 설정해줘야 한다.
    이때 관심있는 mid 즉, 이진탐색을 통해 구해야하는 값은 한번 인출 시 뽑는 금액이다.
    따라서 left 와 right 는 1원 ~ ( ∑ 입력받은 값 ) 이므로

    • left = 1
    • right = ( ∑ 입력받은 값 )

    으로 설정하면 된다.
    그 후 이진탐색 방법대로 조건에 따라 left 를 mid+1 로 할지, right 를 mid-1 로 할지 결정해 값을 update 하며 최적의 값을 찾으면 해결된다!

  • 이진탐색을 하며 신경써야하는 부분은 다음과 같다.

    1. 오늘 써야하는 금액이 한번에 인출 가능한 금액보다 큰 경우
    2. 오늘 써야하는 금액이 내가 현재 가지고 있는 금액보다 큰 경우
    3. 내가 인출한 횟수가 주어진 인출 횟수 M 보다 큰 경우

    이렇게 3가지의 경우를 고려해서 문제를 해결해야한다.

    • 1, 3번의 경우 한번 인출 시 인출하는 금액을 늘리면 되므로 left = mid + 1 로 변경 후 계속해서 이진탐색 진행
    • 2번의 경우 새롭게 인출하면 되므로 현재 가지고 있는 돈을 인출금액인 mid 로 update 하고 현재까지의 인출횟수를 1 증가시킨다.
  • 이렇게 계속해서 이진탐색을 진행하면 문제가 해결되지만, 한가지 주의해야할 점이 있다.
    이 전 이진탐색 문제에서는 조건에 맞는 mid 를 찾으면 그 값을 return 했지만, 여기서는 결괏값을 저장할 어떠한 변수에 중간에 저장해야한다.

    현재 해결한 코드에서는 right 의 값을 mid-1 로 update 하는 부분에서 result 라는 변수에 mid 를 저장해주었다.
    이 말은 현재 mid 값이 현상황에서는 제일 작은 인출금액이라는 것이다.
    그래서 result 라는 변수에 저장 후 이진탐색이 끝나면 이 result 값을 return 하면 된다.

  • k 를 구하는 함수를 따로 정의했으므로, 이 함수를 불러 얻어낸 return 값을 출력해주면 문제 해결!


- 최종 코드

  • c++ code
#include <iostream>
using namespace std;

// N is day, M is # of withdraw
int N, M;

// list of money to spend
int money[100001] = {0, };

// get minimum K with binary search
int get_min_money(int total) {
  int result = 0; // minimum K
  int left = 1;
  int right = total;
  int mid = 0; // withdraw money
  
  while(left <= right) {
    mid = (left + right) / 2;
    int current_money = mid;
    int cnt = 1; // # of withdraw
    bool pass = true; // today_money < withdraw money ?
    
    for(int i = 0; i < N; i++) {
      // if today_money > withdraw money? increase withdraw money
      if(money[i] > mid) {
        pass = false;
        break;
      }
      
      // if today_money > current_money? withdraw money
      if(money[i] > current_money) {
        current_money = mid;
        cnt++;
      }

      // spend money
      current_money -= money[i]; 
    }

    // handle withdraw money
    // case1. (today_money > withdraw money) or (# of withdraw > N)
    // increase withdraw money and search again
    if(!pass || cnt > M) {
      left = mid + 1;
    }

    // case2. not case1
    // decrease withdraw money and search again
    else {
      result = mid;
      right = mid - 1;
    }
  }

  return result;
}

int main() {
  
  // input N and M
  cin >> N >> M;
  
  int total_money = 0;
  // input money to spent
  for(int i = 0; i < N; i++) {
    cin >> money[i];
    total_money += money[i];
  }
  
  // get minimum # of K
  int K = get_min_money(total_money);

  // print result K
  cout << K << endl;

  return 0;
}
  • python code
# input n, m
# n is # of day, m is # of withdraw
n, m = map(int, input().split())

# list of money to spend
money = []
total = 0
for i in range(n):
  a = int(input())
  money.append(a)
  total += a

# binary search
left = 1
right = total
min_k = 0 # minimum k

while (left <= right):
  mid = (left + right) // 2
  current_money = mid # available money
  check = True # check ( today_money < current_money )
  cnt = 1 # # of withdraw

  for value in money:
    # check1. is it possible? (today_money < current_money ?)
    if(value > mid):
      check = False
      break

    # check2. have enough money?
    if(value > current_money):
      current_money = mid
      cnt += 1

    current_money -= value

  # update left and right
  # case1. (today_money > withdraw_money) or (count > M) ?
  if (not check) or (cnt > m):
    left = mid+1

  # otherwise
  else:
    min_k = mid
    right = mid-1

# finish binary search ( = get minimum k )
print(min_k)

0개의 댓글