백준 19949 영재의 시험(자바)

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

19949번: 영재의 시험

 

 

알고리즘 수업을 수강한다는데 5지 선다의 객관식 10문제를 푼다고 한다.

대신 조건이 동일한 번호로 3개 연속 찍지 않는다는 조건이다.

 

입력으로 정답 10개가 주어지는데 한 문제에 1점씩 점수를 준다.

이 때 점수가 5점 이상인 모든 경우의 수를 구하면 된다.

 

문제의 조건 

1. 정답이 3개 연속이 아닌 경우를 생각해야 한다.

2. 영재의 점수가 5점 이상인 경우 카운트를 해야 한다.

 

우선 전체 코드를 보자.

 

import java.util.Scanner;

public class Main {
	static int sum; // 점수의 합
	static int count; // 5이상인 점수의 개수 
	static int[] check; // 내가 체크한 정답
	static int[] right; // 답안지

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		right = new int[10];
		for (int i = 0; i < 10; i++) {
			right[i] = sc.nextInt(); // 답안지 입력 받기
		}
		check = new int[10];
		sum = 0;
		count = 0;

		Back(0);
		System.out.println(count);

	}

	public static void Back(int depth) {
		if (depth == 10) { // depth가 10이 되면 10개 전부 봤으므로
			sum = 0; // sum을 0으로 초기화 하고
			for (int i = 0; i < 10; i++) { // 체크한 답이랑 답안지랑 비교해서 같으면 
				if (right[i] == check[i]) {
					sum++; // 1 더해준다.
				}
			}
			if (sum >= 5) { // sum이 5 이상이면 카운트 1 증가
				count++;
			}
			return;
		}
		for (int j = 1; j <= 5; j++) {
			if (depth > 1 && check[depth - 1] == check[depth - 2] && check[depth - 1] == j) { // 우선 depth가 2 이상이어야 하고
				// 이전 2개의 값이 서로 같고, 현재 내가 고른 정답인 j랑 같으면 3개가 연속되는 경우니 건너뛴다.
				continue;
			}
			check[depth] = j;
			Back(depth + 1);
		}
	}

}

 

알고리즘 분류에도 나와있듯이 전형적인 백트래킹 문제다.

 

 

static int sum; // 점수의 합
static int count; // 5이상인 점수의 개수 
static int[] check; // 내가 체크한 정답
static int[] right; // 답안지

우선 Back메서드 안에서 사용하기 위해 전부 스태틱으로 선언했다.

 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	right = new int[10];
	for (int i = 0; i < 10; i++) {
		right[i] = sc.nextInt(); // 답안지 입력 받기
	}
	check = new int[10];
	sum = 0;
	count = 0;

	Back(0);
	System.out.println(count);

}

main에서 10개짜리 정답 배열을 만들어서 배열에 입력을 받아준다.

그리고 정답을 체크 할 10개짜리 배열을 만들고

sum과 count를 초기화해서 Back 메서드를 돌린다.

 

public static void Back(int depth) {
	if (depth == 10) { // depth가 10이 되면 10개 전부 봤으므로
		sum = 0; // sum을 0으로 초기화 하고
		for (int i = 0; i < 10; i++) { // 체크한 답이랑 답안지랑 비교해서 같으면 
			if (right[i] == check[i]) {
				sum++; // 1 더해준다.
			}
		}
		if (sum >= 5) { // sum이 5 이상이면 카운트 1 증가
			count++;
		}
		return;
	}

우선 종료조건을 먼저 살펴보겠다.

depth가 10이 되면 정답을 전부 체크했다는 소리니 10이 되면 종료를 할 거다.

내부에서 sum을 0으로 초기화해주고 for문을 돌려서 right(정답)이랑 check(내가 쓴 정답)를 확인해서 같으면 점수를 1점씩 더해준다.

sum이 5이상인 경우 count를 하나씩 늘려주고 return을 한다.

 

 

for (int j = 1; j <= 5; j++) {
	if (depth > 1 && check[depth - 1] == check[depth - 2] && check[depth - 1] == j) { // 우선 depth가 2 이상이어야 하고
		// 이전 2개의 값이 서로 같고, 현재 내가 고른 정답인 j랑 같으면 3개가 연속되는 경우니 건너뛴다.
		continue;
	}
	check[depth] = j;
	Back(depth + 1);
}

 

for문을 1부터 5까지 돈 이유는 정답이 1번부터 5번까지 고를 수 있어서 5번을 돌았다.

이전depth가 2개는 있어야 비교가 가능하므로 depth가 1보다는 커야하고

depth-1이랑 depth-2의 값이 같은 상태에서 depth1이 j랑 같으면 3개가 연속해서 정답이 같다는 소리니 건너 뛴다.

아니면 check에 정답을 체크하고 depth+1을 해서 다시 Back을 실행한다.

 

백트래킹을 너무 안풀었다는 생각이 드는 문제였다.

정답률이 80%였는데 문제를 접근하고 생각하고 푸는데 30분 넘게 걸렸었던 문제다.

 

기초를 잡기에는 좋은 문제라고 생각한다.