백준 1463 : 1로 만들기(C언어,C++)

728x90

오늘의 문제

 

오늘은 백준 1463 : 1로 만들기를 풀어보려고 합니다.

실버 3 난이도로 다이나믹 프로그래밍을 연습하는 좋은 문제인데요,

한번 풀어봅시다.

 

 

 

문제

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

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

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

입력

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

출력

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

 

입력과 출력

 

해설

문제를 처음 보면 감이 안 잡힐 수도 있습니다.

"12부터 시작한다면 12에서 3으로 나누기, 2로 나누기, 1 빼기 중에 어떤 연산을 해야 하지?"

이러한 의문을 가질 수도 있습니다.

 

 

이 문제는 이렇게 접근하면 안 됩니다.

거꾸로 생각해야 합니다.

1부터 시작해서 n까지 만들어야 합니다.

각 정수마다 1을 만들기 위해 필요한 연산 횟수를 구해봅시다.

 

1은 바로 만들어졌기 때문에 0회,

 

2는 1을 빼면 되므로 1회,

 

3은 3을 나누면 되므로 1회입니다.

 

 

4는 어떨까요?

일단 4는 2로 나누어 떨어지고 1로도 뺄 수도 있습니다.

2로 나누면 2  , 1로 빼면 3인데

2와 3은 둘 다 1로 만들기 위한 연산 횟수는 1회입니다.

둘은 횟수가 같으므로

4에서 2를 나누거나 1을 빼서 2,3을 만든 다음 1로 나누면

4를 1로 만들 때 필요한 연산 횟수는 2회입니다.

4-> 2,3 -> 1

 

 

5는요? 2와 3으로는 나누어 떨어지지 않으므로 1을 빼는 연산만 가능합니다.

1을 빼면 4인데 4에서 1을 만드는 연산 횟수는 2회 이므로

5에서 1을 만드는 연산 횟수는 3입니다.

5->4->1

 

 

6은?

6은 3으로 나누어지고 2로도 나누어지며 1을 뺄 수도 있습니다.

6의 연산

 

2에서 1 만드는 연산 횟수는 1,

3에서 1만드는 연산 횟수는 1,

5에서 1만드는 연산 횟수는 3입니다.

어떤 숫자를 선택해야 최소 연산이 될까요?

바로 2,3입니다.

그래서 6에서 1을 만드는 연산 횟수는 2입니다.

6-> 2, 3 -> 1

 

 

즉 어떤 수 N의 최소 연산 횟수를 구할 때

N-1, N/2, N/3 이 세 숫자에서 1을 만드는 데 필요한 최소 연산 횟수 중

가장 작은 횟수+1이 N에서 1을 만드는 최소 연산 횟수입니다.

 

 

 

코드

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+1];
    a[1]=0;
    a[2]=a[3]=1;
    for(int i=4; i<=n; i++)
    {
        int s;
        s=a[i-1];
        if(i%3==0&&a[i/3]<s)
            s=a[i/3];
        if(i%2==0&&a[i/2]<s)
            s=a[i/2];
        a[i]=s+1;
    }
    cout<<a[n];
}

 

a [n] 은 n에서 1을 만드는데 필요한 최소 연산 횟수입니다.

a [1], a [2], a [3]은 기본 값이므로 먼저 초기화시켜주고 4부터 n까지 계산을 해줍니다.

반복문에선 a[i-1], a[i/3], a[i/2]값 중 가장 작은 값을 구하고 그 값에 1을 더한 값이 a[i]라고 설정하고 있습니다.

a [n]을 구하기 위해 이전에 만들어준 값을 이용하고 있습니다.

이것이 다이나믹 프로그래밍입니다.

어떠한 큰 문제를 작은 문제로 나누어 해결하는 것입니다.