[C++][DP - 1로 만들기(1463)] bottom - up

백준 1463번 1로 만들기

 

1. 문제 설명

 

• 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

• 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다.
  연산을 사용하는 횟수의 최소값을 출력

 

2. 풀이

횟수를 최소로 하는 경우의 수

1. 3으로 나누어 떨어진다.

2. 짝수지만 1을 빼면 3으로 나누어 떨어진다(x가 2보다 클 때 3번보다 우선 순위 높음 - 경우 따지는 2보다 클때라는 것 상관 없음)

    2-2 짝수지만 2를 빼면 3으로 나누어 떨어진다(x가 8보다 클 때 3번보다 우선순위 높음...)

3. 2로 나누어 떨어진다.

4. 1을 뺀다(홀수고 3으로 나누어 떨어지지 않음)

 

복잡하게 말고 간단하게 생각해보자

역순으로 적용하면 쉽게 해결될 문제였다. 그리고 min 으로 값 비교해주면 끝.

 

 

DP의 bottom-up 방식으로 풀어보자

(queue를 이용해 BFS 방법으로도 풀 수 있다. 이건 다음에)

 

규칙 1. 3으로 나누어 떨어진다

D[n] = D[n/3] + 1  

규칙 2. 2로 나누어 떨어진다

D[n] = D[n/2] + 1 

규칙 3. 1을 뺀다

D[n] = D[n-1] + 1 

 

 

3. 소스코드

//BOJ1463 1로 만들기  
//https://www.acmicpc.net/problem/1463
//DP & BFS

#include <bits/stdc++.h>
//#include <iostream>
//#include <cstring>
//#include <algorithm> 

#define N_MAX (int)1E6+1

using namespace std;

int dp[N_MAX];
int solution(int n)
{
	for (int i = 2; i <= n; i++)
	{
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0)
			dp[i] = min(dp[i / 2] + 1, dp[i]);
		if (i % 3 == 0)
			dp[i] = min(dp[i / 3] + 1, dp[i]);
	}

	return dp[n];

}

int main(){
	dp[1] = 0;
	int n;
	scanf("%d",&n);
	memset(dp,0,sizeof(int)*(n+1));
	printf("%d",solution(n));
}

 

 

풀다보니 c++ 입출력 다시 공부해야겠다.

cin,cout은 시간이 오래걸린다.

 

 

참고사이트

blockdmask.tistory.com/254

melonicedlatte.com/algorithm/2018/09/19/010644.html