[Python] 백준 19949 영재의 시험

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

19949번: 영재의 시험

 

# 19949 영재의 시험

def recur(level, cnt):
    # 문제 10개
    if level == 10:
        num[0] += 1
        return
    
    # 5지선다
    for i in range(1, 6):
        # 문제가 2개 미만이거나 맨 뒤 숫자 두 개가 지금꺼와 다를 경우
        if len(numbers) < 2 or (numbers[-2] != numbers[-1] or numbers[-1] != i):
            numbers.append(i)
            # 정답 맞혔을 때
            if answer[len(numbers) - 1] == i:
                recur(level + 1, cnt + 1)
            else:
                # 남은 문제를 다 맞혀도 5개 이상이 될 수 없는 경우 - backtracking
                if len(numbers) - cnt > 5:
                    numbers.pop()
                    continue
                recur(level + 1, cnt)
            numbers.pop()

answer = list(map(int, input().split()))
numbers = list()
num = [0]
recur(0, 0)
print(num[0])

recur의 cnt는 정답을 맞힌 개수를 의미한다.

 

 

backtracking 부분은 틀린 문제가 6문제보다 많은 경우라고 이해해도 좋을 것 같다.

len(numbers) == 현재까지 출제된 문제

cnt == 현재까지 맞힌 문제

다음과 같이 표기해보자.

cnt : len(numbers) => x / y

 

2 / 7 -> 2문제 맞혔고 7문제 풂 -> 3문제 다 맞히면 5문제 맞힐 수 있음 -> 진행

1 / 7 -> 1문제 맞혔고 7문제 풂 -> 남은 3문제 다 맞혀도 5문제 맞힐 수 없음 -> 다음 단계를 진행하지 않음. backtracking

 

 

recur 함수 안에서 global 선언 없이 num을 자유롭게 사용하기 위해, list 형식으로 num을 데리고 다녔다.