[BOJ] 백준 19949. 영재의 시험

문제

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

19949번: 영재의 시험

---

풀이

백트래킹을 이용한 문제입니다.

 

백트래킹 메서드에 매개변수로 찍었는데 맞은 정답의 수, 현재의 인덱스, 찍은 배열을 전달했습니다.

 이 때 조건에 따라 정답의 수가 5개가 넘으면 ans++를 통해 답을 구합니다.

 

 그리고 3개 이상 연속된 수를 고를 수는 없다는 조건에 맞게 idx가 2이상일 때는 만약 앞의 idx의 값이 두 번 연속되었다면, 그 수는 다음에서 선택할 수 없도록, ban이라는 변수를 선언해 관리했습니다.

 

 만약 찍은 값이 정답이라면, 백트래킹 메서드에 ansCnt + 1을 해주어 백트래킹을 돌리고, 그렇지 않으면 ansCnt 그대로 백트래킹을 돌립니다.

 

아래는 전체 코드입니다.

 

---

소스 코드

import java.util.Scanner;

public class B19949_영재의시험 {
    static int[] ans;
    static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ans = new int[10];
        for(int i = 0; i<10;i++){
            ans[i] = sc.nextInt();
        }
        cnt = 0;
        backTracking(0,0,new int[10]);
        System.out.println(cnt);
    }
    static void backTracking(int ansCnt, int idx, int[] jjik){
        if(idx==10){
            if(ansCnt>=5){
                cnt++;
            }
        }
        else{
            int ban = 0;
            if(idx>=2){
                if(jjik[idx-1]==jjik[idx-2]){
                    ban = jjik[idx-1];
                }
            }
            for(int i = 1;i<=5;i++){
                if(i == ban) continue;

                jjik[idx] = i;
                if(ans[idx]==i){
                    backTracking(ansCnt+1,idx+1,jjik);
                }
                else{
                    backTracking(ansCnt,idx+1,jjik);
                }
                jjik[idx] = 0;

            }
        }
    }
}