0909_algorithm_19949_영재의 시험

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

초기 구상과정

처음 생각했던 과정은 이렇다.

• 재귀호출로 풀기 / DFS로 풀기

1. 스텝 다 끝남 > cnt += 1
2. 점수 5점 이상(backtracking) > cnt += 5 ** (10 - step)
3. DFS(list, step, final, tmp_cnt, point)의 구조

초기코드

def dfs(list, step, final, point, base):
	global cnt
    if s == n:
    	if point >= 5:
        	cnt += 1
        return
    elif point == 5:
    	cnt += 5 ** (10 - s)
        return
    elif point + (final - step) < 5:
    	return        
    else:
    	for i in range(1, 6):
        	base[s] = i
        	if s > 1 and base[s -2] == base[s - 1] == i:
            	continue
            if list[s] == base[s]:
            	point += 1
            dfs(list, step + 1, final, point, base)     

돌아가긴 하는데 답이 다르게 나와서 Debuging하다가 지쳐버렸다...

나름 야심차게 백트래킹도 적용해보고 싶어서 고민했지만 답이 안 나왔다.

최종 제출

def dfs(s):
    global cnt
    if s == 10:
        point = 0
        for j in range(10):
            if ans[j] == base[j]:
                point += 1
        if point >= 5:
            cnt += 1
        return
    for i in range(1, 6):
        if s > 1 and base[s - 2] == base[s - 1] == i:
            continue
        base.append(i)
        dfs(s + 1)
        base.pop()

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

제출했는데 런타임이 너무 길다. python3 코드로 제출하니 시간초과로 패스가 되질 않고 pypy3로 제출하니 정답으로 인정됐다.

개선점

backtracking을 적용해서 시간을 더 단축할 수 있을 것 같다는 확신이 든다. 중간지점에서 가능성을 점검해서 더이상 진행할 수 없는 부분들을 처리하는 방법을 찾아야겠다.