https://www.acmicpc.net/problem/15810
코드설명
파라매트릭서치(Paramatric Search) 를 활용합니다.
사실 처음에 문제를 보고서, HashMap으로 처리하려했습니다. 그래서 코드도 다 작성하고, HashMap으로도 충분히 풀 수 있다고 생각했지만, 각 풍선을 만드는데 걸리는 시간에 따라서 HashMap<풍선만드는데 걸리는 시간, 사람 수> 로 처리하려고 했으나 풍선만드는데 걸리는시간이 만약 3과 5라면, 15에서 최소공배수 꼴로 만나게 되며 HashMap 갱신에 어려움이 있습니다.
이떄, 방법으로는 Node 참조형 클래스를 만들어서 @HashCode, @Equals롤 재정의하여서 같은 <풍선만드는데 걸리는 시간, 사람수> 로 처리할 수도 있으나 해당 방법까지 구현하기에는 올바른 방법은 아닌 것 같아서 중단했습니다.
아쉬운점은, HashMap을 사용할시 같은 중복값이 발생하지 않을경우 중복값이 존재한다는 것을 놓쳤었다는 점입니다.
처음에는 어떤 사람이 '몇시간'걸리게 하는지 처리하는 것이 잘못되었는가 하여 모듈러 연산을 이용하기 위해 Arrays.sort(arR)로 하여 순서대로 접근하도록 처리하는 것과 같은 처리도 진행했으나 결국은 풍선만드는시간이 겹치면서 HashMap의 개수가 아예 합쳐지는 경우가 문제였습니다.
이는 HashMap의 Key 값을 위에서 말햇듯이 Hash함수를 재정의하는 것 밖에 방법이 없어보입니다.
그 대신 파라매트릭 서치로 풀 수 있었습니다.
각 시간이 주어지고, 원하는 풍선 개수가 만들어질떄까지 탐색을 이진탐색으로 진행하면 되겠지요.
이런 문제는 최적화 문제를 결정 문제로 바꿔푼다고 생각하면 됩니다.
문제에서 유의점은 최고값을 설정하는 부분입니다.
풍선 하나를 만드는데 걸리는 시간이 1,000,000(10^6)입니다.
원하는 풍선의 개수가 1,000,000(10^6) 개라고 가정합니다.
스태프의 수가 1명이라고 해봅시다.
그렇다면 시간이 가장 많이 오래걸린다면 10^6 * 10^6 입니다.
해당사항을 고려하여 long형을 사용하여 값을 처리합니다.
코드
정답코드1입니다. 파라매트릭 서치를 활용합니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i=0;i<N; i++) {
arr[i] =Integer.parseInt(st.nextToken());
}
answer = optimize(1, 1000000000000L);
System.out.println(answer);
}
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) {
right = mid;
}else {
left = mid;
}
}
return right;
}
static boolean decision(long size) {
long cnt = 0;
for(int i=0;i<N; i++) {
cnt += size / arr[i];
}
// System.out.println(cnt);
return cnt >= M;
}
}
오답코드1입니다. HashMap으로 풀려고 했던 코드입니다만, 공배수가가 겹칠경우 올바르게 연산하지 못합니다.
HashCode와 Equals를 구현한다면 구현할 수 있다고 생각했지만, Key 값을 활용할경우 너무 복잡해지고 사실상 시간복잡도의 효율이 떨어집니다.
또, 이 문제의 경우 특정 사람의 작업을 진행해서 1씩 올리거나 하는게 아닌, 모든 사람의 작업을 한번에 처리해야 하기 떄문에 이 로직은 적합하지 않습니다.
만약에 특정 인원의 작업을 진행하도록 처리했으면 1씩 증가하도록 처리했으면 됬겠지요.
혹시 각 시간대별 인원을 구해서 처리할 수 있지 않을까? 라는 생각이 듭니다.
하지만, 해당 방식또한 시간초과를 피하기 위해 HashMap으로 저장하여야 하기에 어렵습니다. 이유는 3 5 7 이 주어졌다고 했을떄 항상 3 5 7 순서대로 동작하는게 아니라 3이 더 자주 실행되기 떄문입니다. 예시로, 만약 3과 5가 주어졌다고 해봅시다. 15초에서 만났을경우 이또한 겹치면서 처음에 몇명의 시간대별 인원이 있었는제 확인하지 못하게 됩니다.(물론, 완전탐색으로 배열을 순회하며 한다면 가능하겠지만 완전탐색하게 푼다면 시간초과가 나므로 항상 HashMap을 기준으로 생각해야 하기에 그렇습니다. 매번 배열을 돌면서 확인한다면 결국 10^6 개를 10^6번 확인해야합니다.)
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
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];
static HashMap<Integer, Integer> hashmap = new HashMap<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
hashmap.put(arr[i], hashmap.getOrDefault(arr[i], 0) + 1);
}
Arrays.sort(arr);
solve();
}
static void solve() {
int time = 1;
int modular = 0;
while(M > 0) {
for(Map.Entry<Integer, Integer> entrySet : hashmap.entrySet()) {
System.out.println(entrySet.getKey() + " "+entrySet.getValue());
}
if(hashmap.containsKey(time) == true) {
int ballonCnt = hashmap.get(time);
hashmap.remove(time);
if(ballonCnt > 0) {
M -= ballonCnt;
System.out.println((modular % N));
int workEfficiencyTime = arr[(modular++ % N)];
hashmap.put(workEfficiencyTime + time, ballonCnt);
}
}
time += 1;
}
System.out.println(time - 1);
}
}