백준-16922

0

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

0개의 댓글