[백준 19949번] 파이썬 - 영재의 시험

백준 19949 - 영재의 시험

시간 제한 1초, 메모리 제한 512MB

# 조건

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

입력

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

출력

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

# 접근 방법

• product - 중복순열을 이용하여 모든 조건을 탐색해주어도 되지만 시간이 상당히 걸려서 pypy로만 통과가 된다.
• 따라서 백트래킹을 이용하여 풀어준다.
• numbers에 현재 제출할 답안을 만들건데, 1~5의 수중 현재 길이가 2이하이거나, 연속된 3개의 수가 나오지 않는다면 numbers에 추가하고 재귀를 돌려줄거다.
  • 이 때 중요한 점 2가지는
  • 현재 길이 - 현재 번호까지의 정답 수가 5가 넘는다면 5점이상을 획득할 수 없으므로 continue를 해주고
  • 현재 탐색이 끝났다면 pop을 하여 모든 조합을 탐색해주어야 한다.

product 사용

import sys
input = sys.stdin.readline

from itertools import product

nums = list(map(int, input().split()))
result = 0

for pro in product(range(1, 6), repeat=10):
    temp = 0
    if nums[0] == pro[0]:
        temp += 1
    if nums[1] == pro[1]:
        temp += 1
    for i in range(2, 10):
        if pro[i] == pro[i-1] and pro[i] == pro[i-2]:
            break
        if nums[i] == pro[i]:
            temp += 1
    else:
        if temp >= 5:
            result += 1
print(result)

백트래킹 사용 - python 통과

def dfs(level, cnt):  
    global num  
    if level == 10:  
        num += 1  
        return  

    for i in range(1, 6):  
        if len(numbers) < 2 or (numbers[-2] != numbers[-1] or numbers[-1] != i):  
            numbers.append(i)  
            if answer[len(numbers) - 1] == i:  
                dfs(level + 1, cnt + 1)  
            else:  
                if len(numbers) - cnt > 5:  
                    numbers.pop()  
                    continue  
                dfs(level + 1, cnt)  
            numbers.pop()  


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