[1463] 1로 만들기, c++

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

 

1463번: 1로 만들기

한줄 후기 : dev c++ 때문에 망했어 

아니 dp 배열을 [1000001] 로 선언해 줬는데 dev c++에서 안돌아가는거 ..

그거를 그냥 내봤더니 맞았다고 뜬다 ㅋㅋ.. dev 왜그래?

 

아무튼 백준 다이나믹프로그래밍 들어가면 1번으로 뜨는 문제이다.

 

#include <iostream>
using namespace std;
int main(){
	int dp[1000001]={0};
	int n;
	scanf("%d", &n);
	dp[0] = 0;
	dp[1] = 0;
	for(int i=2; i<=n; i++){
		if(!(i%3)){
			dp[i] = min(dp[i/3], dp[i-1]) + 1;
		}
		else if(!(i%2)){
			dp[i] = min(dp[i/2], dp[i-1]) + 1;
		}
		else{
			dp[i] = dp[i-1] + 1;
		}
	}
	cout << dp[n];
}

그냥 3으로 나누어 떨어지면 dp[i/3]  이랑 dp[i-1] 이랑 더 작은걸 고르면 된다. (3으로 나눌수도 있지만 1을 뺄 수도 있기 때문) 그후 마지막으로 1로 만드는 횟수 1을 더하면 됨.