6236번: 용돈 관리
현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로
www.acmicpc.net
👇 내가 작성한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] account = new int[N];
for(int i = 0; i < N; i++) {
account[i] = Integer.parseInt(br.readLine());
}
int left = Arrays.stream(account).max().getAsInt(); // 모든 지출 중 최대값
int right = Arrays.stream(account).sum(); // 모든 지출의 합
int K = 0;
while(left <= right) {
int mid = (left + right) / 2; // 날짜 별 지출을 mid 금액으로 커버할 수 있는지 확인
int sum = 0;
int count = 1; // 인출 횟수
for(int money : account) {
// 현재까지의 sum에 다음 일자의 금액을 더했을 때, mid보다 크다면 재인출
// 현재 인출한 금액으로는 다음 일자의 금액을 충당할 수 없다는 의미
if(sum + money > mid) {
count++; // 재인출
sum = 0;
}
sum += money; // 현재일자 금액 더하기
}
// 인출 횟수가 M이하인지 검색하고 가능한 최소 금액 찾기
// 인출 금액을 줄여볼 수 있는 여지가 있음
if(count <= M) {
right = mid - 1;
K = mid;
} else left = mid + 1;
// count가 M보다 크다면, 인출 횟수가 너무 많다는 얘기. == mid 금액 증가
}
System.out.println(K);
}
}
'Algorithm & SQL > BOJ' 카테고리의 다른 글
[백준 2573번 / Java] BOJ 2573 : 빙산 (0) | 2024.03.27 |
---|---|
[백준 5052번 / Java] BOJ 5052 : 전화번호 목록 (0) | 2024.03.27 |
[백준 15686번 / Java] BOJ 15686 : 치킨 배달(DFS) (0) | 2024.03.26 |
[백준 14502번 / Java] BOJ 14502 : 연구소(BFS, DFS, 브루트포스) (0) | 2024.03.26 |
[백준 15565번 / Java] BOJ 15565 : 귀여운 라이언(투 포인터) (0) | 2024.03.26 |