Softeer - 인사고과

인사고과 : https://softeer.ai/practice/info.do?idx=1&eid=630

---

Problem

---

Solve

문제를 처음 보았을때 각 난이도에 하나씩 값을 넣어보는 완전탐색밖에 생각이 나지 않았습니다. 하지만 제약조건에서 ci, di가 10^12인것을 보고 완전탐색은 무조건 아니라고 생각이 들었습니다.
결국 소프티어에서 제공하는 풀이를 보고 이진탐색을 이용한 문제임을 알게되었습니다.

만들 수 있는 최대의 세트개수를 구해야하기 때문에 이진 탐색을 통해 세트 개수를 찾아줍니다.

static long binarySearch(long[] tests, int N) {
	long start = 0;
	long end = (long)(2 * Math.pow(10, 12));

	while (start < end) {
		long mid = (start + end +1) / 2;

		if (isAvailable(tests, mid, N)) {
			start = mid;
		} else {
			end = mid - 1;
		}
	}

	return start;
}

세트개수를 0과 cN과 d(N-1)의 최대 합인 2*10^12로 초기화 합니다.
그다음 start가 end보다 작은 경우를 유지하면서 임의의 세트 개수를 구해줍니다.
이때, (start+end+1)/2로 임의값을 구해주어야하는데, 그 이유는 start가 조건을 만족하는 세트수이고 end가 start+1인 경우, start에 대해서 무한루프가 발생하기 때문에 +1을 해주어 이를 예방해주어야합니다.

그 다음은 임의 세트수가 가능한지 여부를 판단해야합니다.

static boolean isAvailable(long[] tests, long tmpSet, int N) {
	long[] copyTests = copy(tests);

	for (int i = 0; i < 2*N-2; i += 2) {
		if (copyTests[i] >= tmpSet) {
			copyTests[i + 2] += copyTests[i + 1];
		} else if (copyTests[i] + copyTests[i + 1] >= tmpSet) {
			copyTests[i + 2] += copyTests[i] + copyTests[i + 1] - tmpSet;
		} else {
			return false;
		}
	}
	return copyTests[2*N - 2] >= tmpSet;
}

ci와 di가 저장되어있는 1차원 배열 tests에서 i레벨에서 임의 세트개수를 만족하도록 di에서 값을 빼와 ci에 채워넣어주어야합니다.

만약 i레벨에서만 사용할 수 있는 문제인 tests[i]의 값이 이미 임의 세트개수 이상이라면 i레벨과 i+1레벨을 사용할수있는 문제인 tests[i+1]를 사용할 필요는 없기때문에 다음 레벨에서만 사용할 수있는 문제 개수인 tests[i+2]에 d(i+1)를 모두 추가해줍니다.
그렇다면 i+2가 i로 갱신되고 이를 반복합니다.

만약 i레벨의 문제로는 임의 세트개수를 만족할수있고 di문제를 함께 사용해야 임의 세트개수를 만족한다면 만족할 만큼만 tests[i]에 저장하고 남은 문제는 tests[i+2]로 넘겨줍니다.
이 또한 i+2가 i로 갱신되고 이를 반복해줍니다.

만약 ci문제와 di문제를 모두 합쳐도 임의 세트개수를 만족할수 없는 경우에는 해당 세트개수는 만족할수 없기 때문에 false를 반환합니다.

위의 과정에서는 N-1레벨까지만 탐색을 하였습니다.
그 이유는 cN은 존재하지만 dN은 존재하지 않기 때문에 앞선 반복문에서 d(N-1)의 값이 tests[2*N-2]에 갱신되어있습니다.
그래서 tests[2*N-2]의 값이 임의 세트개수를 만족하는지 여부를 반환해주면 됩니다.

이를 통해 구할수 있는 세트개수 중 최대의 값을 반환해줄수있게 됩니다.

---

Code

import java.util.*;
import java.io.*;

public class 코딩테스트세트 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());

		StringBuilder sb = new StringBuilder();
		while (T-- > 0) {
			long[] tests = new long[2 * N - 1];
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < 2 * N - 1; i++) {
				tests[i] = Long.parseLong(st.nextToken());
			}

			long testSet = binarySearch(tests, N);
			sb.append(String.valueOf(testSet)).append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static boolean isAvailable(long[] tests, long tmpSet, int N) {
		long[] copyTests = copy(tests);

		for (int i = 0; i < 2*N-2; i += 2) {
			if (copyTests[i] >= tmpSet) {
				copyTests[i + 2] += copyTests[i + 1];
			} else if (copyTests[i] + copyTests[i + 1] >= tmpSet) {
				copyTests[i + 2] += copyTests[i] + copyTests[i + 1] - tmpSet;
			} else {
				return false;
			}
		}
		return copyTests[2*N - 2] >= tmpSet;
	}

	static long binarySearch(long[] tests, int N) {
		long start = 0;
		long end = (long)(2 * Math.pow(10, 12));

		while (start < end) {
			long mid = (start + end +1) / 2;

			if (isAvailable(tests, mid, N)) {
				start = mid;
			} else {
				end = mid - 1;
			}
		}

		return start;
	}

	static long[] copy(long[] tests) {
		long[] copy = new long[tests.length];

		for (int i = 0; i < tests.length; i++) {
			copy[i] = tests[i];
		}

		return copy;
	}
}

---

Result

이분탐색을 통해 구현은 했지만 오답이 나왔습니다. 하지만 생각해보니 ci,di값이 최대 10^12이기 때문에 tests[i]값에는 long타입의 값이 들어가야하는것을 알게되어 타입을 int에서 long으로 모두 변경해주었더니 통과가 되었습니다.
소프티어 질문을 보니 저와 유사한 실수를 하신분이 계서서 이 부분 조심하면 될것 같습니다.

---

Reference

https://www.softeer.ai/community/view.do?idx=673&cd=edu&pageNo=1