(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개 이상 정답인 조건에 맞기 어렵기 때문이죠..

 

 

 

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

 

감사합니다.

 

 

소스코드

---