[백준] 14627 파닭파닭 - 파라매트릭서치(Paramatric Search) + 최적화 문제 결정문제로 바꿔풀기 JAVA

https://www.acmicpc.net/problem/14627

코드설명

파라매트릭서치(Paramatric Search) + 최적화 문제 결정문제로 바꿔풀기 를 활용합니다.

 

유의사항은 자료형입니다.

아래 함수는 최적화 문제를 결정 문제로 바꾼 함수입니다.

static boolean decision(long size) {
    //S가 10^6개.
    //각 파의 길이 L 10^9
    //만약 size가 1 일떄? 10^15까지 가능하므로 long 사용해야함.
    long cnt = 0;
    for(int i=0;i<S; i++) {
        cnt += arr[i] / size;
    }
    return cnt >= C; 
}

이떄, cnt가 long 이어야 하는이유는 만약 파의 Size가 1일때 S가 10^6, L이 10^9 라면, cnt의 경우 10^15 개까지 나옵니다.

그러므로 long 형으로 반환하여야 합니다.

사실 int 형으로도 제출하여도 답은 맞습니다만, 제 생각에는 위와 같은 이유로 long 형을 사용해야 한다고 생각합니다.

아니면 애초에 탐색과정에서 size가 1인 것이 나오지 않는가? 싶기도 합니다.

 

두번쨰도 자료형입니다.

아래의 과정에서 cut * C 가 곱해지면서 int형범위를 벗어날 수 있으므로 long 형을 사용합니다.

System.out.println(answer - cut * C);

 

또 문제에서 파의 길이를 자를 최대 길이를 구하는게 아닌, 라면에 넣을 길이를 구한다는 점을 유의합시다.

저는 해당 사항을 놓쳐서 틀렸습니다.

코드

정답코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R, T, S, C;
	static long answer = 0;
	static int[] arr = new int[1000001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//파의 개수 S = 10^6
		S = Integer.parseInt(st.nextToken());
		//주문받은 파닭의 수 C = 10^6
		C = Integer.parseInt(st.nextToken());
		
		int max = 0;
		for(int i=0;i<S; i++) {
			st = new StringTokenizer(br.readLine());
			//파의 길이 L 10^9 = (10억)
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
			answer += arr[i];
		}
		long cut = optimize(1, max);
		System.out.println(answer - cut * C);
		
	}
	
	static boolean decision(long size) {
		//S가 10^6개.
		//각 파의 길이 L 10^9
		//만약 size가 1 일떄? 10^15까지 가능하므로 long 사용해야함.
		long cnt = 0;
		for(int i=0;i<S; i++) {
			cnt += arr[i] / size;
		}
		return cnt >= C; 
	}
	static long optimize(int lo, int hi) {
		long left = lo - 1;
		long right = hi + 1;
		while(left + 1 < right) {
			long mid = (left + right) / 2;
			if(decision(mid) == true) {
				left = mid;
			}else {
				right = mid;
			}
		}
		return right - 1;
	}
	
}

 

틀린코드입니다. 

틀린점은, 문제에서 주문받은 파닭의 길이만큼만 사용해야 하는걸 놓쳤습니다.

파닭의 크기 C는 정해져있기에 (전체 파의 길이) - (자를 길이) * (C) 를 한 값을 구해야 정답입니다.

저는 모듈러 연산(%, 나머지연산)으로 구해서 파닭의 크기를 무시했습니다... 

 

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R, T, S, C;
	static long answer = 0;
	static int[] arr = new int[1000001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//파의 개수 S = 10^6
		S = Integer.parseInt(st.nextToken());
		//주문받은 파닭의 수 C = 10^6
		C = Integer.parseInt(st.nextToken());
		
		long max = 0;
		for(int i=0;i<S; i++) {
			st = new StringTokenizer(br.readLine());
			//파의 길이 L 10^9 = (10억)
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		long cut = optimize(1, max);
		for(int i=0;i<S; i++) {
			answer += arr[i] % cut;
		}
		System.out.println(answer);
		
	}
	
	static boolean decision(long size) {
		long cnt = 0;
		for(int i=0;i<S; i++) {
			cnt += arr[i] / size;
		}
		return cnt >= C; 
	}
	static long optimize(long lo, long hi) {
		long left = lo - 1;
		long right = hi + 1;
		while(left + 1 < right) {
			long mid = (left + right) / 2;
			if(decision(mid) == true) {
				left = mid;
			}else {
				right = mid;
			}
		}
		return right - 1;
	}
	
	
}