백준-16922

• 조합문제이다.
• 백트래킹을 사용하여 풀면된다고 생각하였다.
• 처음에 코드를 작성하였을 때 시간초과가 발생하였다.

n=int(input())

check=[0 for _ in range(1001)]
ans=0
def solution(depth, num):
    global n_list
    global ans
    if depth==n:
        if check[num]==0:
            ans+=1
            check[num]=1
        return

    Sum=[1, 5, 10, 50]
    for i in range(4):
        solution(depth+1, num+Sum[i])

solution(0, 0)
print(ans)

• 이는 중복된 값까지 계산하여서 그렇다.
• 중복된 계산은 없에는 코드가 필요하였다.
• 아래는 idx 값을 인수로 전달하여 중복된 계산을 하지않게한 코드이다.
• 그리고 불필요한 전역변수는 지웠다.

n=int(input())

check=[0 for _ in range(1001)]
def solution(depth, num, idx):
    if depth==n:
        if check[num]==0:
            check[num]=1
        return

    Sum=[1, 5, 10, 50]
    for i in range(idx, 4):
        solution(depth+1, num+Sum[i], i)

solution(0, 0, 0)
print(sum(check))