문제 탐색하기
입력 자료 정리
- N은 이후 입력값으로 들어올 강의의 수, M은 기준이될 블루레이의 수다
- 이후 들어오는 값은 n만큼 들어오며 각 강의의 길이를 의미한다
해결방법 추론
- i부터 j까지 모든 강의를 더하면서, 그 구간의 개수도 M을 맞춰야하는 문제이다
- N과 M의 최대 입력값을 보았을 때, 브루트포스로는 절대 불가능할 것이라고 쉽게 생각할 수 있었다.
- 그럼 어떤 방법이 있을까? 시간제한에 걸리지 않으면서 할 수 있는
가장 좋은 방법은 이분탐색을 이용하는 것이다 - 배열을 순회하면서 합했을 때,
그 합이 이분탐색의 중간값을 벗어나지 않는 가장 작은 수라면 범위의 개수로 세어준다 - 이렇게 세어준 개수가 M보다 큰지 작은지에 따라 범위를 좁혀나가면서,
최소의 블루레이 크기를 구한다면 해당 문제를 풀 수 있겠다고 생각하였다
시간복잡도 계산
- 이분탐색으로 했을 때 시간제한에 걸리지 않는지 한번 시간복잡도를 계산해보았다
- 나올 수 있는 연산은 일단 이분탐색당 n번의 순회를 하니까 N의 연산은 발생하며,
이분탐색은 나올 수 있는 강의의 최대 길이인 n x m에 log를 씌운 lognm의 연산이 발생할 것이다 - 따라서 총 시간복잡도는 O(nlognm)이 될 것이며,
이렇게 계산했을 때 시간제한을 넘어서지 않는다.
코드 설계하기
입력값 상태 관리하기
- 크기와 기준이될 n과 m은 변수로 관리해준다
- 고정되어 있는 입력값이 들어오기에 배열을 n의 크기로 선언하고
들어오는 값을 순차적으로 넣어주었다.
좌우 값 설계하기
- left와 right는 left는 1, right는 1000000000으로 초기화하였다
- 위와 같이 설정한 이유는 각각 범위의 최소와 최대값이 되기 때문이다.
변수 타입 설정
- 변수타입은 먼저 정답과 이분탐색에서 합산을 할 수 있는 변수에 대해서는
long타입으로 선언하였다 - count도 long타입으로 선언하였는데,
이것은 int형 타입으로 선언해도 범위를 벗어나지 않을것이다.
이분탐색 설계하기
- 일반적인 이분탐색 과정을 진행하면서 합산과 범위의 개수를 세기 위해
변수를 선언하고 0으로 초기화한다 - n만큼 순회하면서 현재 값에다가 누적된 합산을 더했을 때, mid값보다 커진다면
범위를 나타내는 count값을 증가시키고 sum을 0으로 초기화한다 - 조건 검증이 끝나면 해당 조건의 참 거짓 여부없이 sum에다가
현재 원소값을 더해서 저장한다 - 이후 범위의 개수인 count를 m과 비교한다.
만약 count가 작다면 최소값을 찾기 위해 right의 범위를 mid-1로 줄이고, ans에 현재 mid를 넣어준다. - 만약 보다 크거나 같다면 조건자체가 성립되지 않으므로
ans에 넣지 않고 단순 left의 범위만 mid+1로 늘려준다
출력값 설계하기
- 완성한 ans를 출력하면 정답이 될텐데...
시도회차 수정
1회차 시도 실패 분석
- 50%에서 틀렸습니다가 떠버렸다..
원인을 분석해봤을 때, 이분탐색 과정에서 생긴것 같지는 않고,
아마 left와 right초기화 과정에서 생기지 않았을까 생각하였다 - 이분탐색에서 left와 right 범위 설정은 참 쉽지 않다.
문제마다 정하는 방식이 다르기 때문이다 - 그래서 이 부분에서 틀리지 않았을 까 예상하였고,
다시 문제를 살펴보니 이 문제는 블루레이를 담기 위해 정해진 강의의 범위 안에서만
탐색되도록 하는 문제였다 - 따라서 left는 최솟값으로 right는 최댓값으로 설정하고 다시 제출해보았다
2~4회차 시도 실패 분석
- 2회차도 틀렸다... 3회차 4회차까지 다시 시도해보니 무엇이 문제인지 알 수 있었다
- 블루레이 크기의 최소는 주어진 강의 길이중 가장 긴 길이가 될 것이다.
그것 하나만 담는 경우가 있을 것이기 때문이다 - 그렇다면 최대는 무엇이 될까? 생각해보니 모든 강의를 다 더할때가 될것이다
- 따라서 범위를 위 생각에 만족하도록 바꾸고 다시 제출하였다
5회차 시도 성공!
- 5회차 시도에서 드디어 성공하였다
- 초기 값 설정 때문에 까다로운 문제였다.
- 앞으로 초기값 설정을 단순히 입력값 최소 범위 최대 범위로만 잡지 말고, 문제에 맞춰서 설정하도록 생각을 바꿔서 풀어야겠다!
정답 코드
(1회차 시도 실패)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int left = 1;
int right = 1000000000;
long ans = 0;
while(left <= right){
int mid = (left + right) / 2;
long sum = 0;
long count = 0;
for (int i = 0; i < n; i++) {
if(sum + arr[i] > mid){
count++;
sum = 0;
}
sum += arr[i];
}
if(count < m){
right = mid - 1;
ans = mid;
}else{
left = mid + 1;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
(2,3,4회차 시도 실패)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
int left = 1;
int right = 1;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
left = Math.min(left, arr[i]);
right += arr[i];
}
long ans = 0;
while(left <= right){
int mid = (left + right) / 2;
long sum = 0;
long count = 0;
for (int i = 0; i < n; i++) {
if(sum + arr[i] > mid){
count++;
sum = 0;
}
sum += arr[i];
}
if(count < m){
right = mid - 1;
ans = mid;
}else{
left = mid + 1;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
(2~4회차 시도 실패는 비슷해서 4회차만 가져왔다)
(5회차 시도 성공)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
long left = 1;
long right = 1;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
left = Math.max(left, arr[i]);
right += arr[i];
}
long ans = 0;
while(left <= right){
long mid = (left + right) / 2;
long sum = 0;
long count = 0;
for (int i = 0; i < n; i++) {
if(sum + arr[i] > mid){
count++;
sum = 0;
}
sum += arr[i];
}
if(count < m){
right = mid - 1;
ans = mid;
}else{
left = mid + 1;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
문제 링크:
Software Developer