(JAVA) 백준 19949번 : 영재의 시험 -- [백트래킹]

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

19949번: 영재의 시험

 

안녕하세요

 

이 문제는 실버3 문제입니다.

 

총 5^10 경우의 수가 존재하기 때문에, 시간제한인 1초 내에 가능하므로

백트래킹을 활용했습니다.

 

이 때,

문제에서 적혀있듯이

i번째 문제 정답을 적을 때, i-1번째와 i-2번째 적었던 정답이 같으면 i번째 정답은 절대 i-1번째 정답과 같으면 안됩니다.

 

이를 위해 i >=2 인 경우, i-1, i-2번째 정답을 확인하고 같을 때 해당 정답을 제외하고 백트래킹을 진행했습니다.

 

 

다음으로,

5점 이상인 경우를 구하기 때문에

백트래킹 parameter 중 하나로 정답의 개수를 집어넣습니다.

 

그래서 5지선다인 1,2,3,4,5 중 정답과 비교해서 정답인 경우는 count+1한 값을 / 오답인 경우는 count 값을 parameter로 넣고 백트래킹 진행합니다.

이를 위해 백트래킹 시 매 문제마다 내가 입력한 정답과 실제 정답이 같은지를 체크합니다.

 

 

 

마지막으로,

백트래킹 시 최종 10개의 문제의 답을 전부 기입한 경우 정답이 5개 이상인지 체크해서 counting 하는데

메모리 효율성을 위해 남은 문제 개수 + 지금까지 맞춘 정답 개수 < 5 이면 아예 백트래킹 함수를 종료시킵니다.

 

어차피 나머지 문제를 전부 맞춰도 5개 이상 정답인 조건에 맞기 어렵기 때문이죠..

 

 

 

나머지는 아래 소스코드 보시면 이해되실 것 같습니다.

 

감사합니다.

 

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 영재의 시험
	// 백트래킹
	public class p19949 {
	static int count;
	static int[] solutions;
	static final int N = 10;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	solutions = new int[N];
	for(int i = 0; i < N; i++) {
	solutions[i] = Integer.valueOf(st.nextToken());
	}
	backTracking(new int[N], 0, 0);
	System.out.println(count);
	}
	static void backTracking(int[] mySolutions, int solutionCount, int index) {
	if(N - index + solutionCount < 5) { // 남은 문제갯수를 다 풀어도 정답이 되지 못하는 경우
	return;
	}
	if(index == N) { // 10문제를 찍음!
	if(solutionCount >= 5) { // 5문제 이상 풀음!
	count++;
	}
	}
	else {
	int notAnswer = 0;
	if(index >= 2) { // 이전에 2문제 이상 풀었으면 3연속 같은 정답을 적으면 안됨!
	if(mySolutions[index - 1] == mySolutions[index - 2]) {
	notAnswer = mySolutions[index - 1];
	}
	}
	// 5지선다(1, 2, 3, 4, 5)
	for(int i = 1; i <= 5; i++) {
	if(i == notAnswer) { // 3연속 정답은 패스
	continue;
	}
	// 정답이면
	mySolutions[index] = i;
	if(solutions[index] == i) {
	backTracking(mySolutions, solutionCount + 1, index + 1);
	}
	else { // 오답이면
	backTracking(mySolutions, solutionCount, index + 1);
	}
	mySolutions[index] = 0; // 백트래킹 초기화
	}
	}
	}
	}

view raw p19949.java hosted with ❤ by GitHub