티스토리 뷰

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))
함수 설명:
- memo[n]에 값이 존재하면 그 값을 계산하지 않고 그대로 사용
- n이 1이나 0일 경우에 memo에 1을 저장
- n이 1 또는 0인 경우를 모두 카운트했기 때문에 나머지 2 이상의 경우 n-1의 값이 미리 저장되어있다. n에는 n-1의 케이스의 수가 더해져야 하므로 memo[n]에 memo[n-1]의 값을 더해준다.
- "-3"이나 "-2"가 가능 하다면 그 경우도 모두 케이스에 더해준다.
- 마지막으로 memo[n]을 return
해당 문제는 모든 케이스를 카운트하는 문제이다. 따라서 숫자들을 1, 2, 3으로 빼다 보면 0이나 1이 될 것이다. 그때가 하나의 케이스의 끝이므로 그런 경우들을 모두 더하면 주어진 숫자의 케이스의 수를 얻을 수 있을 것이다.
BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm
'알고리즘 이야기 > BOJ 백준 알고리즘' 카테고리의 다른 글
[BOJ] 1904 - 01타일 (0) | 2020.03.22 |
---|---|
[BOJ] 2475번 - 검증수 (feat. map함수) (0) | 2020.03.20 |
[BOJ] 1463번 - 1로 만들기 (feat. python main함수) (0) | 2020.03.18 |
[BOJ] 14717번 앉았다 (feat. sort() 함수) (0) | 2020.03.09 |
[BOJ] 문제집 - N과 M Clear (feat. itertools) (0) | 2020.03.09 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 백준
- 기계식 키보드
- 노개북
- 프로그래머스
- 합격
- 네트워크
- boj
- 후기
- 개발자
- 타입스크립트
- ssi-at
- python
- 프론트엔드
- SW마에스트로
- 개발자북클럽
- 대전
- 오픈소스
- devcon
- python3.8
- 코딩테스트
- 노마드코더
- DevOps
- 알고리즘
- 오픈소스기여
- 개발자밋업
- github
- 회고
- 클린코드
- IT대외활동
- 파이썬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함