문제 ❗
어떠한 숫자에 대해서 이 숫자가 1, 2, 3중 최소 하나를 사용해서 1, 2, 3합의 조합으로 숫자를 만들수있는 경우의수를 묻는 문제이다.
문제의 중요한점은 이 숫자는 양수이고 11보다 작다는 것이다.
즉, 1부터 10까지의 숫자에 대해서만 경우의 수를 알면된다.
시도한 방법 🤣
아주 복잡하게 경우의 수를 모두 찾으려했다.
모두 1로이루어질때 -> 1과 2루어질때 ...
그러나 너무 복잡하고 경우의수도 다양해서 좀처럼 풀리지않았다.
그래서 종이에 쓰면서 풀었다.
1 : (1)
2 : (1, 1), (2)
3 : (1, 1, 1), (1, 2), (2, 1), (3)
4 : (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1)
~
10 : (...), ...
그런데 4를 이루는 1, 2, 3의 조합의 경우의 수를 보면 3을 이루는 조합의 경우의수에 각 1을 더한 값들이고, 2를 이루는 조합의 경우의 수에 각 2를 더한값이고 1을 이루는 조합의 경우의 수에 3을 더한값이다.
여기서 착안을얻어서 5를 이루는 경우의 수는 4를이루는 경우의수 + 3을이루는 경우의수 + 2를 이루는 경우의수를 통해서 했더니 맞았다!
무조건 컴퓨터앞에서 싸우는것보다 안풀리면 직접 손으로 쓰면서 하니 풀리는 경험을 처음으로 했다.
코드 😀
import sys
n = int(sys.stdin.readline().rstrip())
arr = [1, 2, 4]
for i in range(4, 11):
count = 0
for i in range(i - 4, i - 1):
count += arr[i]
arr.append(count)
for i in range(n):
a = int(sys.stdin.readline().rstrip())
print(arr[a - 1])