[백준 1463] 1로 만들기 (Dynamic Programming)

문제: https://www.acmicpc.net/problem/1463

참고 블로그: https://blockdmask.tistory.com/254

 

처음에는 top-down 방식으로 접근해서 삽질했다.

논리가 틀린 것 같진 않은데 시간 초과가 떴다.

 

 

DP카테고리에 있는 문제였고, 아직 DP를 모르기 때문에 구글링했다.

문제 번호를 바로 구글링했는데, 지금 생각해보니 DP를 먼저 검색해볼 걸 그랬다.

결론적으로는 문제 풀면서 DP를 배웠으니 상관없는 것 같기도 하고..

코드 참고한 블로그:  https://blockdmask.tistory.com/254

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int arr[1000001];
  memset(arr, 0, sizeof(int)*(N+1));
 
  arr[1] = 0; //1은 0번
 
  for(int i = 2; i <= N; i++){
    arr[i] = arr[i-1] + 1;
    if(i%2 == 0){
      arr[i] = min(arr[i], arr[i/2]+1);
    }
    if(i%3 == 0){
      arr[i] = min(arr[i], arr[i/3]+1);
    }
  }
 
  cout << arr[N];
  return 0;
}

 

https://blockdmask.tistory.com/257?category=250801

이건 같은 블로거가 Queue를 이용해서 BFS로 푼 방법이다.

나는 DFS로 풀어서 시간 초과가 나왔던 것 같다.

 

Dynamic Programming 동적 계획법:

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postView