https://www.acmicpc.net/problem/16401
- 오늘의 학습 키워드
과자 나눠주기
- 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt(); // 조카 수
int N = sc.nextInt(); // 과자 수
int[] snacks = new int[N];
for (int i = 0; i < N; i++) {
snacks[i] = sc.nextInt();
}
int result = solution(M, snacks);
System.out.println(result);
}
public static int solution(int M, int[] snacks) {
int maxLen = 0;
for (int len : snacks) {
maxLen = Math.max(maxLen, len); // 가장 긴 과자 길이
}
int left = 1;
int right = maxLen;
int result = 0;
while (left <= right) {
int mid = (left + right) / 2;
long count = 0;
for (int len : snacks) {
count += len / mid; // mid 길이로 나눌 수 있는 조각 수
}
if (count >= M) {
result = mid; // 가능한 경우, 더 큰 길이도 시도
left = mid + 1;
} else {
right = mid - 1; // 불가능하면 더 작은 길이 탐색
}
}
return result;
}
}
- 오늘의 회고
만약 이 문제를 완탐으로 풀면 10억번을 확인해야 해서 시간 초과가 난다.
때문에 이분 탐색으로 풀어야 한다.
'📝 끄적끄적 > 항해99 코테 스터디' 카테고리의 다른 글
99클럽 코테 스터디를 수료하며 (0) | 2025.04.28 |
---|---|
99클럽 코테 스터디 13일차 TIL + JadenCase 문자열 만들기 (0) | 2025.04.16 |
99클럽 코테 스터디 12일차 TIL + 포도주 시식 (0) | 2025.04.15 |
99클럽 코테 스터디 10일차 TIL + 병든 나이트 (0) | 2025.04.12 |
99클럽 코테 스터디 9일차 TIL + 저울 (0) | 2025.04.10 |
99클럽 코테 스터디 8일차 TIL + 한국이 그리울 땐 서버에 접속하지 (0) | 2025.04.10 |