1463번 - 1로 만들기 풀이

문제

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

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

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

입력

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

출력

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

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

문제풀이

이 문제의 경우 분류가 DP로 들어가있다.

이런 경우, 항상 끝이 좋지 않았는데, 이유는 절대 단순히 풀어서 안된다는 점.

void Recur(int n)

{

    if(n ==1 ) return; 

 if(n % 3 ==0)  ~~

else ~~

}

이렇게 풀면 답이안나온다. 결론은 DP문제는 항상 점화식을 세워서 하거나 어떠한 규칙을 찾아야 한다.

구하고자 하는 것이, 최소 횟수이기 때문에 배열의 N 번째가 몇 번의 횟수를 가지느냐! 라는 생각을 하면 쉽게된다.

다음과 같이 구하면 된다.

 

1. 배열 선언 및 입력받기

#define max 1000001

int n;
int dp[max] = {0,};

int main(void)
{
	cin >> n;
    
	return 0 ;
}

입력의 조건에 10의 6승 == 1,000,000 이기때문에, 1칸 여유를 두어 1,000,001을 define해주었다.

입력받을 수인 n, 100만개의 정수형 배열 을 선언했고, 그 수를 0으로 초기화해주었다.

 

2. 규칙 고려하기

Top - Bottom , Bottom - Top 이런게 있는데, 자세히는 모르겠고, Bottom - Top이 쉬운문제부터 해결해나가 ~뭐 문제를 해결한다~ 라는 의미라고한다. 

 

규칙을 다음에 설명할 것이긴 한데, 이렇게 나온다.

처음은 당연히 안나올 것이고, N-1 은 0씩 계속해서 상승할 것이지만, 매 루프마다 최솟값을 넣기 때문에, N-1은 이전 루프의 최솟값 +1 로 연산 할 수 있다.

 

다시말해 규칙은 이전 루프의 나눈 수의 값 +1 vs (2로 나눠진 횟수) or (3으로 나눠진 횟수) 이다.

 

3. 코드작성

#include <iostream>
using namepspace std;

#define max 1000001
int dp[max] = {0,} ;
int n;

int main(void)
{
	cin >> n;
    
    for(int i = 1; i < n+1; i++)
    {
    	if(i == 1)
        	dp[i] = 0;
        else
        {
        	dp[i] = dp[i-1]+1; // 이전 나눠진 수의 + 1
            
            if(i % 3 == 0)  // 3으로 나눠질 수라면
            	dp[i] = min(dp[i], dp[i/3]+1); // 지금 있는 수와 +1한 수를 비교
            
            if(i % 2 == 0)  // 2으로 나눠질 수라면
            	dp[i] = min(dp[i], dp[i/2]+1);   
        }
    }
    
    cout << dp[n] << endl; // 입력 수의 최솟값 수 

}

으로 작성할 수 있다.