[백준 1463번] - 1로 만들기

1463번: 1로 만들기

[문제 설명]

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.15 초 (하단 참고)	128 MB	209950	68556	43766	32.177%

문제

정수 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 유형에 대해 알 수 있었다.

처음엔 문제가 정수 X를 1로 만들기로 되어있어서 숫자 X를 /3, /2, -1 등을 수행하면서 문제를 풀려고 시도했었다.

 

그것보다 1부터 X까지 만들수있는 최소 연산 횟수를 저장하면서 만드는게 더 쉬워보였다.

만약 입력이 1,2,3이 들어온다면

1은 연산을 할 필요가 없으니 0

2는 x2 연산 or +1 연산으로 1

3은 x3 연산으로 1

위의 연산 횟수를 미리 벡터 DP에 저장해둔다.

 

그렇게 4부터 X까지 반복문을 돌면서

dp[i] = dp[i-1] +1 을 기본 값으로 넣어두고,

index 값 i가 2의 배수이면 2로 나누어서 dp[i]값과 dp[i/2] + 1 값과 비교해서 넣어준다.

index 값 i가 3의 배수이면 3으로 나누어서 dp[i] 값과 dp[i/3] +1 값과 비교해서 넣어준다.

 

위의 연산이 어떤 의미인지 예를 들어 설명하면

만약 i가 12이면

첫번째는, 11까지 연산된 횟수(5)에 +1을 연산하는 경우를 저장하는것이고 -> 6

두번째는, 6(2)까지 연산된 횟수에 x2 연산하는 경우를 비교하는것이고 -> 3

세번째는, 4(2)까지 연산된 횟수에 x3 연산하는 경우를 비교하는것이다 -> 3

 

이중 가장 작은 값을 dp에 저장하는것을 X가 될때까지 반복하고, dp[X]의 값을 출력하면 정답이 된다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

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

int main()
{
    int N;
    cin >> N;
    vector<int> v(N+1,0);
    v[1] = 0;
    v[2] = 1;
    v[3] = 1;
    
    for(int i = 4; i <= N; i++)
    {
        v[i] = v[i-1] + 1;
        if(i%2 == 0) v[i] = v[i] < v[i/2] + 1 ? v[i] : v[i/2] + 1;
        if(i%3 == 0) v[i] = v[i] < v[i/3] + 1 ? v[i] : v[i/3] + 1;
    }
    
    printf("%d\n", v[N]);
}