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);
}
}
import java.util.*;
class Solution {
public String solution(int[] numbers) {
String[] arr = new String[numbers.length];
for(int i = 0; i < numbers.length; i++) {
arr[i] = String.valueOf(numbers[i]);
}
// 두 수를 합친 값을 기준으로 내림차순
// o1 : 30, o2 : 5 일 경우, 305와 530 중 더 큰 값 비교
Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
// 정렬된 배열의 맨 처음이 0이라면 0으로만 되어있음. 0 반환
return arr[0].equals("0") ? "0" : String.join("", arr);
}
}
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
Arrays.sort(times); // 이분 탐색을 위해 정렬
long left = 0;
long right = (long) n * times[times.length - 1]; // 최악의 경우 고려
while(left <= right) {
long mid = (left + right) / 2;
long sum = 0; // 심사한 인원
for(int time : times) {
sum += mid / time;
}
// n명 심사해야하는데 못했다면, 시간이 더 필요하기 때문에 left 옮겨줌
if(sum < n) left = mid + 1;
// n명 이상 했다면 시간을 줄여서 최적의 시간을 확인해보기
else {
right = mid - 1;
answer = mid;
}
}
return answer;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N, M;
static int min = Integer.MAX_VALUE;
static int[] selected;
static List<int[]> house = new ArrayList<>();
static List<int[]> chicken = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
selected = new int[M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
int value = Integer.parseInt(st.nextToken());
if(value == 1) house.add(new int[] {i, j}); // 집 좌표 저장
else if(value == 2) chicken.add(new int[] {i, j}); // 치킨가게 좌표 저장
}
}
dfs(0, 0);
System.out.println(min);
}
public static void dfs(int L, int start) {
if(L == M) { // 유지하는 치킨집 M개 선택 완료되면 dist 메소드 실행
dist();
return;
}
// 유지할 치킨집 M개 조합하여 selected배열에 인덱스 저장
for(int i = start; i < chicken.size(); i++) {
selected[L] = i;
dfs(L + 1, i + 1);
}
}
public static void dist() {
int sum = 0;
for(int[] h : house) {
int tempMin = Integer.MAX_VALUE;
for(int idx : selected) { // 유지할 치킨집 M개의 인덱스가 담겨져있는 배열
int[] hCur = chicken.get(idx);
int distance = Math.abs(h[0] - hCur[0]) + Math.abs(h[1] - hCur[1]); // 거리 차이 구하기
tempMin = Math.min(tempMin, distance); // 집에서 가장 가까운 치킨집 선택
}
sum += tempMin; // 선택한 치킨거리 누적합
}
min = Math.min(sum, min); // 치킨거리 최솟값 구하기
}
}
느낀 점 및 정리 ✍️
1. dfs에서 조합 for문 돌릴 때 원하는 방식의 조합 조건이 바로바로 떠오르질 않는다 ㅠㅜ 문제 많이 풀면서 익혀야겠다
