티스토리 뷰

한번에 깔끔하게 클리어!

1463번 풀고 바로 풀어본 문제이다. DP의 개념을 좀 접한 뒤에 풀어본 문제라 이제는 상향식으로 풀어야 쉬운지 하향식으로 쉬운지가 보인다. 


문제 후기

이번문제에서는 하향식으로 접근할 때 쉬웠다. 더하기를 이용해 주어진 숫자를 표현하는 가짓수를 구하는 문제라서 그런지 주어진 숫자에서 1, 2, 3 중에 뺄 수 있는 값으로 빼서 끝가지 뺐을 때의 가짓수를 카운트하면 쉽게 해결이 되었다. 정답 코드에서 자세하게 설명하겠다.

 

문제 풀이

import sys


def make123(n):
    
    if memo[n] > 0:
        return memo[n]
    
    if n == 1 or n == 0:
        memo[n] = 1
        return memo[n]

    memo[n] += make123(n-1)
    if n-3 >= 0:
        memo[n] += make123(n-3)
    if n-2 >= 0:
        memo[n] += make123(n-2)
    return memo[n]


if __name__ == "__main__":
    n = int(sys.stdin.readline())
    for _ in range(n):
        k = int(sys.stdin.readline())
        memo = [0] * (k + 1)
        print(make123(k))

 

함수 설명:

  1. memo[n]에 값이 존재하면 그 값을 계산하지 않고 그대로 사용
  2. n이 1이나 0일 경우에 memo에 1을 저장
  3. n이 1 또는 0인 경우를 모두 카운트했기 때문에 나머지 2 이상의 경우 n-1의  값이 미리 저장되어있다. n에는 n-1의 케이스의 수가 더해져야 하므로 memo[n]에 memo[n-1]의 값을 더해준다.
  4. "-3"이나 "-2"가 가능 하다면 그 경우도 모두 케이스에 더해준다.
  5. 마지막으로 memo[n]을 return

해당 문제는 모든 케이스를 카운트하는 문제이다. 따라서 숫자들을 1, 2, 3으로 빼다 보면 0이나 1이 될 것이다. 그때가 하나의 케이스의 끝이므로 그런 경우들을 모두 더하면 주어진 숫자의 케이스의 수를 얻을 수 있을 것이다.

 

BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm

 

공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함