[백준 문제풀이] 얼렁뚱땅 15989 1, 2, 3 더하기 4 풀이

얼렁뚱땅 백준 문제풀이

[백준 문제풀이] 얼렁뚱땅 15989 1, 2, 3 더하기 4 풀이

MOSTAR 2022. 10. 5. 00:58

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

15989번: 1, 2, 3 더하기 4

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2

www.acmicpc.net

# 백트레킹으로 풀기 : 시간초과 및 메모리초과

import sys

sys.setrecursionlimit(10**7)
tc = int(sys.stdin.readline())
num = [1,2,3]

def dfs(idx, sum_, answer) :
    global count
    if answer == sum_ :
        count+=1
        return
    
    if answer < sum_ :
        return

    for k in range(idx,3) :
        temp_ = sum_ + num[k]
        if temp_ == answer :
            dfs(k,temp_,answer)
            break
        elif (temp_ < answer) :
            dfs(k,temp_,answer)

# visited를 어떻게 잡아야 할까앙
for i in range(tc) :
    what = int(sys.stdin.readline())
    count = 0
    dfs(0, 1, what)
    dfs(1, 2, what)
    dfs(2, 3, what)
    print(count)

# dp : 성공

tc = int(input())

dp = [1] * 10001

for i in range(2,10001) :
    dp[i] += dp[i-2]

for i in range(3, 10001) :
    dp[i] += dp[i-3]

for _ in range(tc) :
    n = int(input())
    print(dp[n])

코드 자체가 막 어려운 건 아닌데, 이걸 생각하는게 어려운 거 같다.

며칠 백트레킹 풀었다고 또 백트레킹으로 푼 멍청구리 ..

dp 진짜 문제 연습해야게따 그럼 뿅