[백준 14697번] 방 배정하기 (java)

백준 14697번 : 방 배정하기

14697번: 방 배정하기

 

브루스포스 알고리즘이며, 나는 재귀를 이용하여 문제를 풀었다.

 

재귀의 base case를 방 배정을 성공(true)하느냐, 실패(false)하느냐로 나눴는데, 

꼭 모든 방에 학생을 배분할 필요가 없으므로, 아직 모든 방에 배정하기 전인데 남은 학생 수가 0이 되어도 탈출 조건이 될 수 있다.

 

<base case>

- 모든 방에 배정 여부와 관계없이 남은 학생이 0명이면, true를 반환

- 마지막 방까지 배정했을 때, 남은 학생이 존재하면 false를 반환

 

재귀함수를 호출할 때는, 방에 배정하고 남은 학생을 인수로 넘겨준다.

 

소스코드:

 

	import java.io.*;
	public class n14697 {
	static int N;
	static int[] room = new int[3];
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] sarr = br.readLine().split(" ");
	for (int i = 0; i < 3; i++)
	room[i] = Integer.parseInt(sarr[i]);
	N = Integer.parseInt(sarr[3]);
	boolean res = solve(0, N);
	if (res)
	bw.write(1 + "\n");
	else
	bw.write(0 + "\n");
	bw.flush();
	}
	public static boolean solve(int idx, int n) {
	if (idx == 3 && n > 0)
	return false;
	if (n == 0)
	return true;
	for (int i = n / room[idx]; i >= 0; i--) {
	if (solve(idx + 1, n - i * room[idx]))
	return true;
	}
	return false;
	}
	}

view raw BaekJoon 14697.java hosted with ❤ by GitHub