BOJ 1463번 :: 1로 만들기

#문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

#작성 코드

#include <iostream>
using namespace std;

int cnt=0;
int memo[1000001];

int op(int n){
	memo[1] = 0;
	memo[2] = 1;
	memo[3] = 1;
	for(int i=4; i<=n; i++){
		memo[i] = memo[i-1]+1;
		if( i%2 == 0 ){
			memo[i] = min( memo[i/2]+1, memo[i] );
		}
		if( i%3 == 0 ){
			memo[i] = min( memo[i/3]+1, memo[i] );
		}
		// 1을 더해서, 2를 곱해서, 3을 곱해서 i가 되는 경우 중 연산 최솟값 
	}
	return memo[n];
}
int main(){
	int N;
	cin>>N;
	cout<<op(N);
	return 0;
}

##

입력받을 수 N은 최대 10^6이 될 수 있으므로,

어느 수 i를 만들 때까지 수행된 연산 횟수를 저장할 배열 memo[10^6+1]을 선언한다.

1에서부터 출발하여 N을 만드는 연산 횟수는

   1. 1을 더해서 n-1에서 n만들기

   2. 2를 곱해서 n/2 에서 n만들기 @n%2==0인 경우.

   3. 3을 곱해서 n/3에서 n만들기 @n%3==0인 경우.

이 경우들 중 연산 횟수가 최소가 되는 경우를 memo[n]에 저장한다.

 

#191216 review

위의 방식은 1을 n으로 만드는 방식이다.

문제 형식과 같이 n을 1로 만드는 방식으로 문제를 풀어보고싶었다.

int make1_solve_topdown(int n){
    for(int i=1; i<=n; i++){
        make1_d[i] = 2000000000;
    }
    make1_d[n] = 0;
    
    for(int i=n; i>0; i--){
        if( i%3==0 ){
            make1_d[i/3] = min(make1_d[i]+1, make1_d[i/3]);
        }
        if( i%2==0 ){
            make1_d[i/2] = min(make1_d[i]+1, make1_d[i/2]);
        }
        make1_d[i-1] = min(make1_d[i]+1, make1_d[i-1]);
    }
    return make1_d[1];
}

for문 내부의 i/3, i/2, i-1 케이스 연산은 순서에 관계없다.

위의 코드와 다르게 꼭 설정해야 하는 것은 make1_d[n] = 0을 제외한 모든 인덱스 값을 아주 큰 수로 초기화시켜야 한다는 것이다.

min값을 계산할 때 초기값이 0이라면 절대 업데이트 되지 않는다.

---

TOP-DOWN 방식

N을 1로 만드는 최소 횟수 = f(N)이라고 하면

만약 N이 1인 경우에는 f(N)=0을 리턴해버린다.

dp(N)이 이미 계산되었다면(dp는 연산의 최소횟수가 될 수 없는 -1로 초기화해둬야한다.) dp(N)을 리턴한다.

새로 dp(N)을 계산해야 하는 경우...

dp(N) = f(N) = min( f(N/3)+1, f(N/2)+1, f(N-1)+1 ) 이 된다. return dp(N)

 

BOTTOM-UP 방식

N=1 -> F(N)=0

N=2 -> F(N)=1

N=3 -> F(N)=1

N=4 -> F(N) = min( F(N-1)+1, F(N/2)+1 )          4는 3의 배수가 아니므로...

...

F(N) = F(N-1)+1

만약 N이 2의 배수이면 F(N) = min( F(N),  F(N/2)+1 )

만약 N이 3의 배수이면 F(N) = min( F(N), F(N/3)+1 ) 으로 갱신해준다.