[백준 9095번] 파이썬 - 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

 

# 조건

• 정수 4를 1,2,3의 합으로 나타내는 방법은 총 7가지
• 합을 나타낼 때는 수를 1개이상 사용
• 정수 n이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구하라

 

# 나의 접근 방법

• 1,2,3으로 나타낼 수 있는 경우의 수를 구하는 문제이므로 6의 경우 1,1,1,1,1,1 에서 3,3 까지 오면된다.
• 1만 이용하는 방법에서 총 1의 개수 = 주어지는 n
• 이 때, 1,2,3으로 이루어진 길이 n의 중복순열을 구한 후 합이 n과 같다면 카운트 해준다.
• 길이 n은 2가 1개 들어갔을 때를 최대로, 3이 최대로 들어갔을 때의 길이를 최소로 하여 반복문으로 구해준다.

DP 문제였지만 DP스럽지 않게 풀었다.

다른 분들의 코드를 보니

• 1, 2, 3을 [1,2,3]만을 이용하여 구성하는 방법의 수는 각각 1개, 2개, 4개이다.
• 여기서 4를 123만을 이용하여 구하는 경우의 수는 7로 f(1) + f(2) + f(3)과 같다.
• 따라서 점화식 f(n) = f(n-3) + f(n-2) + f(n-1)을 구해서 풀어주었다.

---

1. 내가 푼 코드

import sys  
from itertools import product  
input = sys.stdin.readline  
  
  
T = int(input())  
  
for tc in range(T):  
    N = int(input())  
    # 1,2,3으로 이루어진 리스트 만들어준 후  
    num = [1,2,3]  
    # 모두 1로 구성된 경우 +1 해준 후 반복문 돌리는데  
    cnt = 1  
    # 2하나와 1로 구성된 경우의 길이 = N-1  
    # 3이 최대로 들어간 경우의 길이 = N//3 이므로    
    # 해당 길이의 순열을 반복문을 통해 생성해준다.    
    for i in range(N-1, N//3-1, -1):  
        # 한 숫자가 여러번 반복될 수 있는 중복 순열 이용  
        # product(iterable, repeat='반복수'        
        arr = list(product(num, repeat=i))  
        for i in arr:  
            if sum(i) == N:  
                cnt +=1  
  
    print(cnt)

 

 

2. 다른 분들 코드 (dp이용, dfs이용)

t = int(input())
dp = [0,1,2,4]

for i in range(4,11):
    dp.append(dp[i-1]+dp[i-2]+dp[i-3])

for i in range(t):
    n = int(input())
    print(dp[n])

 

--

t= int(input())

def solution(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    elif n==3:
        return 4
    else:
        return solution(n-1) + solution(n-2) +solution(n-3)

    
for i in range(t):
    n = int(input())
    print(solution(n))

 

• 문제야 어떻게든 풀면 장땡이지만, 위 3가지 코드를 모두 제출해보았을 때, 내가 짠 코드가 메모리, 시간 효율이 모두 제일 낮았다.

• 익숙해질 때까지 많이 풀어보고, 생각을 좀 더 깊게하는 습관을 들이면 좋을 것 같다.