[백준] 19949번 영재의 시험 - Java, 자바

난이도

실버 3

문제

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

풀이

백트래킹으로 해결

1. 정답 배열을 arr에 저장
2. youngjae라는 배열을 만들어 백트래킹으로 정답 배열 만들기
   여기서 주의할 것!
   찍을 때 3개의 연속된 문제의 답은 같지 않아야하므로
   depth가 2 이상일 때, youngjae[depth-1], youngjae[depth-2]의 값과 현재 찍으려는 값(i)이 같을 때는 i를 정답에서 제외 시킨다.
3. 종료조건) depth == 10 인 경우
   정답 배열과 영재 배열을 비교해서 점수가 5점 이상일 때 경우의 수 ans를 증가시킨다.

코드

package 백트래킹;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ19949 {
    static int[] answer;
    static int[] youngjae;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        answer = new int[10];
        youngjae = new int[10];

        for (int i = 0; i < 10; i++) {
            answer[i] = Integer.parseInt(st.nextToken());
        }
        ans = 0;
        back(0);
        System.out.println(ans);
    }

    static void back(int depth) {
        if (depth == 10) {
            int cnt = 0;
            for (int i = 0; i < 10; i++) {
                if (answer[i] == youngjae[i]) {
                    cnt++;
                }
            }
            if (cnt >= 5) {
                ans++;
            }
            return;
        }

        for (int i = 1; i <= 5; i++) {
            if (depth >= 2) {
                if (youngjae[depth - 1] == i && youngjae[depth - 2] == i) continue;
            }
            youngjae[depth] = i;
            back(depth + 1);
        }
    }

}