[백준] 19949. 영재의 시험

문제

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

19949번: 영재의 시험

 

설계

- DFS, 백트래킹

- level(수준): 10 / branch: 5

 

백트래킹을 적용했으나 파이썬으로 제출했을 경우 시간초과에 걸렸다. pypy 로 제출하여 통과했으나 메모리나 시간이 많이 소요되어 시간복잡도를 좀 더 줄여야 하는 코드라고 생각한다.

def dfs(level):
    global cnt

    if level == 10:
        score = 0
        for i in range(10):     # 10문제를 모두 풀었으면 몇 문제가 맞았는지 검사
            if arr[i] == path[i]:
                score += 1
            if i >= 2:          # 백트래킹, 3개의 연속된 문제의 답은 같지 않게 한다.
                if path[i] == path[i - 1] == path[i - 2]:
                    return
        if score >= 5:          # 5점 이상인 경우를 카운트 한다.
            cnt += 1
        return

    for i in range(1, 6):
        path.append(i)
        dfs(level+1)
        path.pop()      # 원상복구

arr = list(map(int, input().split()))
path = []
cnt = 0         # 5점 이상일 경우 카운트한다.

dfs(0)
print(cnt)