[백준_19949번] 영재의 시험

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

19949번: 영재의 시험

[문제]

 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행히도 문제가 5지 선다의 객관식 10문제였다. 찍기에도 자신 있던 영재는 3개의 연속된 문제의 답은 같지 않게 한다는 자신의 비법을 이용하여 모든 문제를 찍었다. 이때 영재의 점수가 5점 이상일 경우의 수를 구하여라. 문제의 점수는 1문제당 1점씩이다.

 

[입력 조건]

시험의 정답이 첫 줄에 주어진다.

 

[코드]

import java.util.Scanner;

public class BaekJoon_19949 {
	static int result=0;
	static int[] score=new int[10];
	static int[] choice=new int[10];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		// 각 문제의 정답 저장
		for(int i=0;i<10;i++)
			score[i]=sc.nextInt();

		dfs(0);
		System.out.println(result);
	 }
	
	static void dfs(int depth) {
		// 10 문제 모두 답을 선택했다면 점수 계산
		if(depth==10) {
			int sum=0;
			for(int i=0;i<10;i++) {
				if(score[i]==choice[i])
					sum++;
			}
			// 5점이 넘었다면 경우의 수 count
			if(sum>=5)
				result++;
			
			return;
		}
		
		for(int i=1;i<6;i++) {
			/*
			 * 이전 두 문제와 답이 같으면 안되기 때문에 
			 * 두 문제 이상으로 푼 경우에 이전 문제와 그 이전 문제와 답이 같은 경우는 넘어간다. 
			 */
			if(depth>1&&choice[depth-1]==i&&choice[depth-2]==i)
				continue;
			
			choice[depth]=i; // 5지선다형 중 하나 선택
			dfs(depth+1); // 재귀호출
			choice[depth]=0; // 값 초기화
		}
	}

}

 

[고찰]

 이번 문제는 백트래킹을 사용하여 해결하였다. 이때 백트래킹을 사용하여 탐색해야 하는 조건은 5지선다형 문제의 답 이기 때문에 for문은 1부터 5까지 돌려야 한다. 그리고 영재는 연속된 3개의 답은 같지 않게 선택하기 때문에 문제를 2개 이상 푼 경우에 이전 2 문제와 답이 같다면 해당 경우는 넘어가도록 한다. 여기서 실수를 범했는데 자바는 == 연산을 연달아 쓰지 못한다는 점을 까먹었다. (choice[depth-1]==i&&choice[depth-2]==i) 이 부분을 실수로 (choice[depth-1]==choice[depth-2]==i) 이렇게 코딩하여 오류가 발생해 이유를 찾는데도 시간이 좀 걸렸다. 이런 실수는 반복하지 말야겠다.