문제 링크
2613번: 숫자구슬
첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 숫자 구슬은 M개의 그룹으로 나누어야 합니다.
2. 그룹을 나누었을 때 각 그룹의 합 중 최대값이 최소값을 결과로 출력합니다.
3. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야한다.
4. 만약, 그룹의 합의 최대값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 이분 탐색을 통해서 최소값 탐색합니다.
3. 탐색을 통해 얻은 최소 값을 결과로 출력합니다.
이분 탐색
이분 탐색으로 찾는 값은 문제 응답에 대한 최소값입니다.
최소값과 최대값을 기준으로 이분 탐색을 진행하며, 중간값을 기준으로 M개의 그룹으로 만들 수 있는지 확인합니다.
► 이분 탐색이 마친 뒤 얻은 값은 M개의 그룹을 만들 수 있는 최소값이 됩니다.
이분 탐색에서 발생하는 상황
1. 중간값을 기준으로 M개의 그룹을 만들지 못하는 경우.
2. 중간값을 기준으로 M개의 그룹을 만들 수 있는 경우.
right = mid
M개 그룹 만들 수 있는지 확인
숫자구슬을 그룹으로 만들 때에는 연속해있어야 합니다.
즉, 순차적으로 그룹을 만들어서 중간값보다 커지면 새로운 그룹을 만드는 과정을 반복합니다.
예를 들어, 중간값이 15일 때
17일 때에는 중간값(15)보다 커지기 때문에 그 이전까지만 그룹을 형성하고, 다시 그룹을 만들어 나아가는 방식입니다.
위 과정을 거쳐서 M개의 그룹을 만들 수 있는지 확인합니다.
주의해야 할 점.
이 문제에서는 M개의 그룹에는 숫자구슬이 반드시 1개가 포함되어 있어야 합니다.
M개의 그룹을 만들다가 아래의 조건을 만족한 경우, 각 그룹에는 숫자구슬이 1개씩 되어야 합니다.
남은 숫자구슬의 개수 == 만들어야하는 남은 그룹 개수
※ 그룹의 숫자구슬이 1개 있더라도 중간값을 초과할 수 있습니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 8
M : 3
숫자구슬
2. 이분 탐색을 통해서 최소값 탐색합니다.
최소/최대값 구하기
이분 탐색 진행
M(3)개의 그룹을 만들 수 없습니다.
M(3)개의 그룹을 만들 수 있습니다.
M(3)개의 그룹을 만들 수 없습니다.
M(3)개의 그룹을 만들 수 있습니다.
M(3)개의 그룹을 만들 수 없습니다.
3. 탐색을 통해 얻은 최소 값을 결과로 출력합니다.
탐색이 끝났을 때, 최소값(left, 17)이며, 해당 상황일 떄 각 그룹의 숫자구슬의 개수는 { 4, 2, 2 }입니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 숫자구슬의 정보를 띄어쓰기 기준 나누었습니다.
- 숫자구슬을 토대로 최소/최대값을 구합니다.
- search함수를 이용하여 숫자구슬의 그룹 최소값을 탐색합니다.
- 탐색을 통해 얻은 그룹의 최소값을 Bufferedwriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 이분 탐색을 통해서 그룹의 최소값을 탐색합니다.
- marbleCheck함수는 M개의 그룹을 만들 수 있는지 확인합니다.
결과코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
static int[] groupMarbleCnt;
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
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());
st = new StringTokenizer(br.readLine()," ");
int[] marble = new int[N];
groupMarbleCnt = new int[M];
int sum = 0;
int min = Integer.MAX_VALUE;
//숫자구슬 정보 저장 및 최소/최대값 구하기
for(int i=0;i<N;i++){
marble[i] = Integer.parseInt(st.nextToken());
min = Math.min(min, marble[i]); //최소값 : 숫자구슬 최소값
sum += marble[i]; //최대값 : 모든 숫자구슬의 합
}
//이분 탐색을 통해 최소값 구하기
int result = search(marble, min, sum, N, M);
//최소값 BufferedWriter 저장
bw.write(String.valueOf(result));
bw.newLine();
//각 그룹의 숫자구슬 개수 BufferedWriter 저장
for(int i=0;i<M;i++){
bw.write(String.valueOf(groupMarbleCnt[i]));
bw.write(" ");
}
bw.flush(); //결과 출력
bw.close();
br.close();
}
//이분 탐색을 통해 최소값을 탐색하는 함수
public static int search(int[] marble, int min, int sum, int N, int M){
int left = min;
int right = sum;
while(left < right){
int mid = (left + right) / 2;
//M개의 그룹을 만들 수 있을 때
if(marbleCheck(marble, mid, N, M)){
right = mid;
}else{ //M개의 구슬을 만들 수 없을 때
left = mid + 1;
}
}
return left; //최소값 출력
}
//중간값이 최소값이라고 가정할 때 M개의 구슬을 만들 수 있는지 확인하는 함수
public static boolean marbleCheck(int[] marble, int mid, int N, int M){
//현재 그룹 개수
int gCnt = 1;
//탐색한 숫자구슬 개수
int mCnt = 0;
//현재 그룹의 숫자구슬의 합
int sum = 0;
int[] marbleCnt = new int[M];
//M개의 그룹을 만들 수 있는지 확인하기
for(int i=0;i<N;i++){
//그룹의 개수가 M개보다 크거나, 단일 숫자 구슬이 최소값보다 클 때
if(gCnt > M || marble[i] > mid){
return false;
}
//최소값보다 커졌을 때거나, 남은 숫자구슬 개수 == 남은 그룹 개수
if(sum + marble[i] > mid || N-i <= M - gCnt){
//현재 그룹에 속한 숫자구슬 개수 저장
marbleCnt[gCnt-1] = mCnt;
gCnt++; //새로운 그룹 생성
mCnt = 1; //새로운 그룹에 숫자구슬 저장
sum = marble[i]; //새로운 그룹에 맞는 합 초기화
}else{ //그룹에 숫자구슬 추가
mCnt++;
sum += marble[i];
}
}
//M개의 숫자그룹을 만들 수 없을 때
if(gCnt > M){
return false;
}
//M개의 숫자구슬을 만들 수 있을 때
marbleCnt[gCnt-1] = mCnt;
//현재 M개을 만들었을 때 각 그룹의 속한 숫자구슬 개수 저장
for(int i=0;i<M;i++){
groupMarbleCnt[i] = marbleCnt[i];
}
return true;
}
}'백준' 카테고리의 다른 글
| [백준, Java] 1184번, 귀농, (누적합) (0) | 2024.03.20 |
|---|---|
| [백준, Java] 14224번, 작은 정사각형2, (이분 탐색) (0) | 2024.03.14 |
| [백준, Java] 1438번, 가장 작은 직사각형, (완전 탐색) (0) | 2024.02.20 |
| [백준, Java] 15912번, 우주선 만들기, (DP) (0) | 2024.02.08 |
| [백준, Java] 17307번, 색깔 통일하기, (누적합) (0) | 2024.02.06 |
댓글