(Python/🥈2)백준 알고리즘 19949번: 영재의 시험

문제 바로가기 

영재의 시험 바로가기

문제:

컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행히도 문제가 5지 선다의 객관식 10문제였다. 찍기에도 자신 있던 영재는 3개의 연속된 문제의 답은 같지 않게 한다는 자신의 비법을 이용하여 모든 문제를 찍었다. 이때 영재의 점수가 5점 이상일 경우의 수를 구하여라. 문제의 점수는 1문제당 1점씩이다.

입력:

 

시험의 정답이 첫 줄에 주어진다.

출력:

영재의 점수가 5점 이상일 경우의 수를 출력하여라.

import sys

def dfs(depth):
    global cnt
    if depth == 10: # 깊이가 10 이면
        s = 0 # 비교해야할 값
        for j in range(10): # 두개를 비교하면서
            if li[j] == ans[j]: # 맞으면
                s += 1 # 비교해야할 값 올려주고
        if s >= 5: # 5개 이상 맞으면
            cnt += 1 # 카운터를 올려줌
        return ;
    for i in range(1, 6): # 5지 선다임 5개중 1개 넣어야함
        if depth > 1 and li[depth-2] == li[depth-1] == i: # depth > 1 안넣으면 인덱스 오류
            continue # 숫자 3개 연속이면 넘겨줌
        li.append(i) # 아니면 더해주고
        dfs(depth+1) # 다음숫자 탐색
        li.pop() # 백트래킹

ans = list(map(int, input().split()))
li, cnt = [], 0
dfs(0)
print(cnt)

 

 

다른 방법

# 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:
                if len(numbers) - cnt > 5: # 남은 문제 다 맞혀도 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])

이렇게 푼다고 한다. 

if len(numbers) - cnt > 5:
                    numbers.pop()
                    continue

이걸로 남은 문제를 다 맞혀도 5점이 넘지 않으면 탐색도 안 한다. 이 부분에서 시간을 줄인다.