6236 - 용돈 관리

 

6236번: 용돈 관리

#include <stdio.h>

const int LN = 1e5 + 30;

int N, M, R;
int COST[LN];

void init() {
  scanf("%d %d", &N, &M);

  for (int n = 0; n < N; ++n) {
    scanf("%d", &COST[n]);
  }
}

int cal(int money) {
  int balance = money;
  int count = 1;

  for (int n = 0; n < N; ++n) {
    if (money < COST[n]) {
      return 0;
    }

    if (balance < COST[n]) {
      balance = money;
      count++;
    }

    balance -= COST[n];

  }

  return count <= M;
}

void bs(int s, int e) {
  if (s > e) { return; }

  int m = (s + e) / 2;

  if (cal(m)) {
    R = m;
    bs(s, m - 1);
  } else {
    bs(m + 1, e);
  };
}

int main(void) {
  freopen("6236.txt", "r", stdin);

  init();

  bs(1, 1e9);

  printf("%d", R);

  return 0;
}

 

이분 탐색 초기 범위 조심