https://www.acmicpc.net/problem/1463
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
Bottom-up 방식과 Top-down 방식이 있다.
아무래도 생각하면서 풀기에는 Bottom-up 방식이 더 쉬운 것 같다.
+ 똑같이 풀어도 Top-down은 계속 시간초과가 나는데.. 아직 해결 못함
* dp[N] 의 최솟값은 dp[N-1]+1 / dp[N/3]+1 / dp[N/2]+1 중 최솟값이다.
아래는 Bottom-up 방식,,
for문을 통해서 계속해서 나아가는 방식!
아래는 top-down 방식
함수내에서, 재귀처럼 계속 호출하는 것이다.
?????? 왜 시간초과 나냐구????????
오랜만에 dp 푸니까 어렵네 🤯
참고한 사이트
'Algorithm Study' 카테고리의 다른 글
| [BOJ] 11726번: 2*n 타일링 (0) | 2022.05.04 |
|---|---|
| [BOJ] 1003: 피보나치함수 / DP, JAVA (0) | 2022.05.03 |
| [BOJ] 2468: 안전영역/ JAVA, DFS (0) | 2022.05.02 |
| [BOJ] 3184번 : 양 / JAVA, DFS (0) | 2022.04.26 |
| [BOJ] 1780번: 종이의 개수/ JAVA, 재귀 (0) | 2022.04.25 |