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