728x90
처음에 풀 때는 5까지 구해보고 풀어봤다.
•n = 1 -> (1)
1개
•n = 2 -> (1 + 1) , (2)
2개
•n = 3 -> (1 + 1 + 1), (2 + 1) ,(1 + 2), (3)
4개
•n = 4 -> (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2+ 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1)
7개
• n = 5 -> (1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 1 + 2 + 1), (1 + 1 + 3), (1 + 2 + 1 + 1), (2+ 1 + 1 + 1), (1 + 2 + 2), (2 + 1 + 2), (2 + 2 + 1), (1 + 3 + 1), (3 + 1 + 1), (2 + 3), (3 + 2)
13개
그랬더니 규칙이 보였다.
바로 1+2+ 4 = 7 , 2+ 4 + 7 = 13
그래서 바로 코드로 가서 풀었다.
T = int(input())
def sum(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4
else:
return sum(n - 1) + sum(n - 2) + sum(n - 3)
for i in range(T):
n = int(input())
print(sum(n))
그러고 나서 다른 코드를 보다가 오늘 배운 백트래킹 개념이 나와서 이것도 참고했다.
T = int(input())
def bt(value, sum):
global count #전역 변수 global
if sum >= n: # 1,2,3을 더하는 가지를 치는데 sum을 초과하면 더이상 진행 x
return
sum += value
if sum == n:
count += 1
bt(1, sum)
bt(2, sum)
bt(3, sum)
for i in range(T):
n = int(input())
count = 0
bt(0, 0)
print(count)
이 코드 같은 경우에는 backtracking을 사용해서 풀었는데 코드만 보고 이해하기 어려워서 직접 그려서 표현해 봤다.
이런 식으로 가지치기하다가 sum >= n이면 백 트래킹 하여 그 부분을 들어가지 않는다.
728x90
'알고리즘 > 파이썬' 카테고리의 다른 글
[파이썬 알고리즘] 104.leetcode _ 이진트리의 최대 깊이 (0) | 2022.05.23 |
---|---|
[파이썬 알고리즘] 이진트리 기초 개념(1) (0) | 2022.05.23 |
[파이썬 알고리즘] 78.leetcode - 부분집합 (0) | 2022.05.20 |
[파이썬 알고리즘] 그래프(DFS, BFS) 개념 (0) | 2022.05.20 |
[파이썬 알고리즘] 리트코드200 - 섬의개수(Number of Islands) (0) | 2022.05.19 |