[BOJ/JAVA] 백준 1561번 : 놀이 공원

1561번: 놀이 공원

 

 

 

---

 

 

 

• 풀이

 

 

놀이공원에서 M개의 놀이기구를 타기위해 N명의 사람들이 기다리고있다. N명의 사람들은 운행중이지 않은 놀이기구 중 가장 앞 번호의 놀이기구를 탄다고 했을 때, 맨 마지막인 N번째 사람은 M개중 몇번째 놀이기구를 탈 것인가?? 를 묻는 문제입니다.

 

일단, N의 값이 20억이기 때문에 1명, 1명 몇번째 놀이기구를 타는지를 계산하면 적어도 1초에 1억번 계산한다 했을 때 20초가 걸린다고 생각하여 시간 초과가 뜰 것이라고 생각했습니다.

 

시간을 줄이기 위해 다른 방법을 생각해야만 했는데, 사람을 세는 것이 아닌 몇 초 후가 지났을 때 몇명이 탔는가에 대해 초점을 맞추면 이분 탐색이 가능합니다. 이분 탐색은 시간복잡도가 O(log N)으로 매우 빠르기때문에 시간안에 들어올거라 생각했습니다.

 

이분 탐색의 풀이 과정은 아래와 같습니다.

1. 이분 탐색을 통해 마지막 사람이 타는 시간이 몇초 후인지 알아냅니다.
2. 이분 탐색을 통해 얻어온 시간 전에 몇명의 사람이 탔는지 구합니다. (예를들어, 10초 후에 N번째  사람이 탄다고 가정하면 9초 후에 몇명의 사람이 탔는지 더해놓습니다.)
3. 반복문을 통해 N 번째 사람이 타는 시간에 N번째 전 사람들이 타는 횟수를 더해줍니다. 더하다가 N번째 사람이 탑승하면 해당 놀이기구 번호를 저장해주고 반복문을 종료합니다. 

 

참고

right 값을 선언할 때 long으로 타입변환을 시키지 않으면 제대로된 값을 구해오지 못합니다.

N을 int, M을 int로 받아왔을 때 N값이 20억, M값이 1, 놀이기구 시간이 2일 경우, N/M*(놀이기구 중 최대 시간)을 하면 40억으로 int형으로는 다 표현할 수 없기 때문입니다. 

 

---

 

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int N, M, answer;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		N = in.nextInt();
		M = in.nextInt();
		answer = 0;
		array = new int[M+1];
		int max = 0;
		
		if(N <= M) {
			answer = N;
			return;
		}
		
		
		for(int i = 1; i <= M; i++) {
			array[i] = in.nextInt();
			max = Math.max(max, array[i]);
		}
		
		long high = binarySearch(max);
		
		long sum = M;
		for (int i = 1; i <= M; i++)
			sum += (high - 1) / array[i];

		for (int i = 1; i <= M; i++) {
			if (high % array[i] == 0)
				sum++;

			if (sum == N) {
				answer = i;
				break;
			}
		}
	}
	
	private static long binarySearch(int max) {
		long left = 0;
		long right = (long) N/M*max;
		
		while(left <= right) {
			long mid = (left + right) / 2;
			
			long sum = M;
			for(int i = 1; i <= M; i++) {
				sum += mid/array[i];
			}
			
			if(sum < N)
				left = mid +1;
			else
				right = mid -1;
		}
		
		return left;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}