[백준/Python] 19949. 영재의 시험

 

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

 

🔹 접근 방법

백트래킹을 이용해서 문제를 풀어야겠다고 생각했다.

답을 선택하면 visited에 답을 저장해두고 3개 연속으로 같은 정답을 선택하지 않도록 했다.

또한 답을 선택할때 정답일 경우 점수를 1점씩 올렸다.

 

 

---

 

🔹 코드 구현

def dfs(n, score):
    global cnt
    # 10문제를 모두 푼 경우
    if n >= len(answers):
        if score >= 5:
            cnt += 1  # 5개 이상 정답을 맞췄을 경우 카운트 증가
        return

    for i in range(1, 6):  # 1~5 중에서 선택
        # 연속된 3개의 답이 같은 경우 제외
        if visited[n-1] == visited[n-2] == i:
            continue

        visited[n] = i  # 현재 문제의 답 설정
        if answers[n] == i:  # 정답일 경우
            dfs(n+1, score+1)
        else:  # 오답일 경우
            dfs(n+1, score)
        visited[n] = 0  # 백트래킹 (되돌아가기)

# 입력 및 초기화
answers = [0, 0] + list(map(int, input().split()))  # 인덱스를 2부터 시작하기 위해 패딩 추가
visited = [0] * len(answers)  # 선택한 답을 저장하는 리스트
cnt = 0  # 정답 조합의 개수

# DFS 실행
dfs(2, 0)  # 문제는 2번 인덱스부터 시작
print(cnt)  # 가능한 정답 조합 개수 출력