[코딩테스트C++] 1로 만들기

오늘의 문제

https://www.acmicpc.net/problem/1463

1로 만들기

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;
// 1로 만들기
int solution(int a){
    vector<int> arr(a+1, INF);
    arr[a] = 0;
    for(int i=0;i<a-1;i++){
        int num = a-i;
        if(arr[num] != INF){
            int count = arr[num]+1;
            if(num % 3 == 0)
                arr[num/3] = min(arr[num/3], count);
            if(num % 2 == 0)
                arr[num/2] = min(arr[num/2], count);
            arr[num-1] = min(arr[num-1], count);
        }
    }
    return arr[1];
}

풀이 법

• DP로 풀기위해서는 배열안에 무엇이 들어가야하는지 생각하는것
• 문제에 답이있다. 답을 구하는 것을 넣으면 된다. 즉 연산을 한 횟수를 넣는다.
• 입력한 숫자에서 시작되므로 0으로 시작하고 모두 INF로 초기화한다.
• INF로 초기화한 이유는 비교연산을 하기 위해서이다. 더 작은것을 선택하려면 INF가 필요하다.
• 해당 숫자에서 3또는 2로 나눠지면 나눠진 숫자의 배열에 현재 연산횟수에 1을 더한 값을 넣는데, 여기서 중요한 점은 min연산을 이용하는 것이다. 그래야 최소횟수가 나온다. 만약 과정에서 거쳐가는 횟수를 구한다면 1씩 더해준다.
• 모든 연산이 끝난 후 1인경우의 배열의 값을 출력하면 끝

모범 답안

#include <cstdio>

using namespace std;

int i;

int Fast(int i)
{
    if(i<=1) return 0;
    int A = Fast(i/3) + i % 3 + 1;
    int B = Fast(i/2) + i % 2 + 1;
    return A < B ? A : B;
}

int main()
{
    scanf("%d",&i);
    printf("%d",Fast(i));
}

배울 점

• 이사람은 재귀로 문제를 풀었다. 일종의 DFS 2,3으로 나눠진 결과중에서 작은것을 출력
• 1씩 작아지는 것은 어차비 모든 경우에서 더해지는 것이므로 그냥 전체결과에 1을 더했다.
• 굉장히 축약이 잘되어있다.