[백준/C++] 1463번 1로 만들기 - (1)

백준 1463번 1로 만들기

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

 

 

이 문제는 DP로 풀어야한다. (필자는 BFS로 풀었다가 시간초과가 떴다.. 코드는 올려놓겠다)

 

정수 N을 입력했을 때 1로 만들기 위한 최소 연산횟수를 구하는 문제이다.

즉, 입력에 대한 연산횟수의 최소값에 따라 그 연산횟수를 응용하는 것이다.

dp[i] = dp[i-1] + 1;
        if(i%2==0) dp[i] = min(dp[i], dp[i/2]+1);
        if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1);

이 부분의 경우 if문이 연달아 2개이기 때문에 조건이 성립되면 결국에 min(dp[i-1]+1, dp[i/2]+1, dp[i/3]+1)을 비교한 것이다!!

Bottom up 방식으로 밑에서부터 차근차근 최소 횟수를 구해서 결국 원하는 값의 최솟값을 구하는 형식이다. 

맞는 코드 (DP 방식)

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int N;
    scanf("%d",&N);
    int dp[10000001];

    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    for(int i=4; i<=N; i++)
    {
        dp[i] = dp[i-1] + 1;
        if(i%2==0) dp[i] = min(dp[i], dp[i/2]+1);
        if(i%3==0) dp[i] = min(dp[i],dp[i/3]+1);
    }
    printf("%d\n",dp[N]);
    return 0;
}

틀린 코드 (BFS 방식)

 

#include<iostream>

using namespace std;
int result = 0;
int compare = 100000;
int func(int n, int result) {
	if (n == 1) {
		if (compare == -1) compare = result;
		else if (result < compare) compare = result;
		return compare;

	}
	if (result >= compare) return result;
	if (n % 3 == 0 && compare > result) func(n / 3, result + 1);
	if (n % 2 == 0 && compare > result) func(n / 2, result + 1);
	if(compare > result)func(n - 1, result + 1);

}
	/*if (n % 3 == 0) {
		
		n = n / 3;
		result++;
		func(n,result);
	}
	else if (n % 2 == 0) {
		func(n - 1);
		n = n / 2;
		result++;
		func(n);
	}
	else {
		n -= 1;
		result++;
		func(n);
	}*/


int main() {

	int n;
	cin >> n;

	cout << func(n, 0) << endl ;

	return 0;
}