BOJ. 9095 1, 2, 3 더하기 (Python)

[ 문제 ]

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

[ 나의 풀이 ] 

🔸 접근 방법

주어진 숫자를 1, 2, 3 으로 빼서 0이 될 때까지 뺀다. 0이 되는 경우에는 return 한다.

1, 2, 3으로 뺄때 값을 문자열로 저장한다. 문자열 값은 answer라는 list에 저장한다.

해당 list에 존재하지 않으면 문자열 값을 추가한다.

list의 길이가 곧 합을 나타낼 수 있는 방법의 수가 된다.

 

🔸 풀이 코드

# n이 1, 2, 3의 합으로 구성되어 있는 경우를 찾는 함수
def find(n, string):
	# n의 값이 0인 경우
    if n == 0:
    	# 그동안 값을 뺀 string이 저장하지 않은 경우에만 answer list에 값 저장
        if not string in answer:
            answer.append(string)
        return 
    
    # n의 값이 0이 아닌 경우. 1, 2, 3 순서대로 빼고, 뺀 숫자를 문자열로 기록
    for num in [1, 2, 3]:
        if n >= num:
            find(n-num, string + str(num))
        else:
            continue

# 테스트 케이스 개수 T
T = int(input())

# 테스트 진행하는 반복문
for _ in range(T):
	# 뺀 숫자를 저장할 list
    answer = list()
    
    # 인풋 정수값 N
    N = int(input())

	# find 함수를 통해 N값이 1, 2, 3으로 이루어진 경우를 answer에 저장
    find(N, '')

	# answer의 길이 출력
    print(len(answer))

[ pair의 풀이 ]

🔸 접근 방법

pair는 피보나치 수열의 규칙이 있다는 것을 찾아냈다..... 어케 했지... 😯

그 전 3개의 합이 그 다음 정수의 값이 된다.

전체 정수가 11까지여서 11까지의 피보나치 수열 값을 다 저장해두고 값을 출력했다.

짱👍

 

🔸 풀이 코드

t = int(input())

arr = [0 for _ in range(11)]
arr[1] = 1  # 1
arr[2] = 2  # 1+1, 2
arr[3] = 4  # 1+1+1, 1+2, 2+1, 3

for i in range(4, 11):
    arr[i] = sum(arr[i-3:i])

for _ in range(t):
    n = int(input())
    print(arr[n])

 

 

pair 의 github : https://github.com/Ui-Seok