문제.
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는
1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 들기 때문에 꼭 같은 크기로 해야 한다.
입력 예시
9 3
1 2 3 4 5 6 7 8 9
답 : 17
나의 답변
public class Main {
public int solution(int n, int m, int[] songs) {
int answer=0;
/*
DVD의 크기용량 최소, 최대 범위
용량이 최소 : 값 중 최대값이 최소용량 크기.노래가 쪼개지지않을 정도의 크기
용량이 최대 : 모든 값을 다 한 곳에 넣을 때의 크기
*/
int max=Integer.MIN_VALUE;
int sum=0;
for(int i=0; i<n; i++) {
if(songs[i]>max) {
max=songs[i];
}
sum+=songs[i];
}
int lt=max, rt=sum;
while(lt<=rt) {
// 이진탐색을 위한 중간값 설정(DVD크기 임시값을 중간값으로)
int mid=(lt+rt)/2;
if(possible(songs, mid, m)) {
// DVD 용량 크기를 줄임
rt=mid-1;
}else {
// DVD 용량 크기를 늘림
lt=mid+1;
}
}
answer=lt;
return answer;
}
private boolean possible(int[] songs, int mid, int size) {
// DVD 개수, 노래길이 합
int cnt=1, sum=0;
for( int song : songs ) {
// 노래길이합이 DVD크기보다 크다면
if(song+sum>mid) {
// DVD개수 +1
cnt++;
// 노래길이 합은 reset
sum=0;
}
sum+=song;
}
// DVD개수가 주어진 DVD개수를 넘어가지 않으면 범위를 더 줄여도 됨
if(cnt<=size) return true;
else return false;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] songs = new int[n];
for( int i=0; i<n; i++ ) {
songs[i]=sc.nextInt();
}
System.out.println(T.solution(n, m, songs));
}
}
배열 최대값과 합을 구하는 또 다른 방법
배열의 최대값 구하는 방법 : Arrays.stream(배열).max().getAsint();
배열의 합을 구하는 방법 : Arrays.stream(배열).sum();
결정 알고리즘 동작 방식
- 문제에 대한 가능한 해의 범위를 설정
- 가능한 해의 범위에서 중간값을 선택
- 선택된 중간값을 기반으로 "예" 또는 "아니오"로 답할 수 있는 질문을 제시하며 범위 좁힘
- 찾고자하는 값이 중간 값보다 작다면 시작포인터 동일, 끝 포인터 : 중간 값 인덱스 -1
- 찾고자하는 값이 중간 값보다 크다면 시작포인터 : 중간 값 인덱스+1, 끝 포인터 동일
- 위 과정을 반복한다.
이분 검색과 결정 알고리즘 공통점과 차이점
정렬된 배열에서 이진 탐색 알고리즘을 사용한다.
- 결정 알고리즘
- 주어진 배열에서 특정 값이 존재하는지를 확인 ( 예 / 아니오 )
- 이분 검색
- 주어진 배열에서 특정한 값을 찾는데 사용
