[코딩테스트] 완전 탐색 연습

많이 나올 거 같은 점화식 유형

 

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

9095번: 1, 2, 3 더하기

def DFS(n) : 
    if n == 1 : 
        return 1
    if n == 2 : 
        return 2
    if n == 3 : 
        return 4
    
    return DFS(n-1)+DFS(n-2)+DFS(n-3)

N=  int(input())

for _ in range(N) :
    num = int(input())
    print(DFS(num))

 

문자열과 수를 이용한 완전 탐색을 사용한 단순한 구현 문제 

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

1065번: 한수

 

다음 '셀프 넘버' 문제는 특별히 DFS를 활용하여 풀어보았다.
먼저 기초 일의 자리 자료들 [1,2,3,4,5,6,7,8,9] 들을 활용하여 만들 수 있는 한수들은, 자신들의 수에 자릿수 하나를 더 더하는 방식이므로, 2배를 해준 것과 같다. 
예를 들어 1이라는 생성자를 이용하여 만들 수 있는 수는 1(자기 자신) + 1(자릿수에 해당하는 수) 이므로 2다. 이렇게 먼저 dp table에 만들 수 있는 녀석들은 전부 visited 처리를 해주고,
아직 방문하지 않는 녀석들이 생성자가 존재하지 않는 녀석들이기에 쭉 DFS로 search해주는 방식으로 구현하였다. 

memo = {}

for i in range(1,10000+1) :
    memo[i] = False

for one_int in range(10) :
    memo[one_int*2] = True

def d(n) :
    if n > 10000 :
        memo[n] = True
        return 
    
    for k in str(n) :
        n+=int(k)
        
    memo[n] = True
    d(n)

for i in range(10,10001) :
    d(i)

for last in range(1,10001) :
    if not memo[last] :
        print(last)