[백준][C++] 1463 1로 만들기

1463. 1로 만들기

1463번: 1로 만들기

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

너무나도 그리디 문제 같이 생겼는데...

그리디로 계속 풀다가 결국 포기하고 DP로 푼 문제. 문제만 보면 그리디로 풀 생각을 하는 걸 고쳐야겠다고 생각했다.

 

처음 접근들은 앞서 말했다싶이 그리디로 했다. 그리고 생각나는 방법은 모두 해봤다.

• 가장 먼저 3으로 나누고, 2로 나누고, 1 빼기
• 가장 먼저 3으로 나누고, 1 뺀 값이 3의 거듭제곱이라면 1 빼기, 그리고 2 나누기
• N이 3의 거듭제곱이 될 때까지 1 빼기
• N이 3과 2의 공배수가 될 대까지 1 빼기

...

상당히 상당한... 방법들이었지만, 지금 모아보니 질보단 양에 초점을 맞춘 것 같다.

 

일단 이 로직이 안 되는 이유는 3에 초점을 맞췄기 때문!!

 

또, 나누는 것만이 최적해가 아니라는 것도 알아야 한다... 1로 뺄 때가 더 효율적일 때가 있다는 것.

그리디 문제가 아니라면, 3과 2의 공배수일 때 2로 나누는 것이 더 최적해일 수 있다는 생각이 들었다.

 

그래서 DP로 풀었다. 애초에 DP 문제집에 있는 문제를 왜 그리디로 풀었는지는 모르겠다만... 도전은 중요한 거니까 ㅎ_ㅎ

로직은 이러하다.

 

알고리즘 설계

1. 1~10^6까지의 길이의 정수형 배열을 만든다. 배열엔 i로 가기 위한 최소 연산 횟수를 넣어줄 것!
2. 배열의 초깃값을 check[1] = 0, check[2] = 1, check[3] = 1로 만들어준다. 연산이 1, 2, 3을 기반으로 하기 때문.
3. 4~N까지 반복문을 돌려가며 배열을 채워간다.
   • 2와 3의 공배수일 땐 check[2/i]+1와 check[3/i+1] 중 더 작은 것을 넣어준다.
     • 3으로 나누는 것만이 최적해는 아니기 때문!
   • 2의 배수일 땐 check[2/i]+1와 check[i-1] 중 더 작은 것을 넣어준다.
   • 3의 배수일 땐 check[3/i]+1와 check[i-1] 중 더 작은 것을 넣어준다.
   • 그 외엔 check[i-1]을 넣어준다.

 

코드로 구현해봤다.

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;

int check[1000001] = { false, };

int main()
{
    int num;
    cin >> num;

    check[1] = 0;
    check[2] = 1;
    check[3] = 1;

    for (int i = 4; i <= num; i++)
    {
        int prev = check[i - 1];

        if (i % 6 == 0)
        {
            check[i] = min(check[i / 2], check[i / 3]) + 1;
        }
        else if (i % 2 == 0)
        {
            check[i] = min(prev, check[i / 2]) + 1;
        }
        else if (i % 3 == 0)
        {
            check[i] = min(prev, check[i / 3]) + 1;
        }
        else
        {
            check[i] = prev + 1;
        }
    }

    cout << check[num];
}

어려웠던 문제였다...

풀고 나니 간단한 문제였는데, DP로 생각하는 방식이 어려웠다...

 

특히 num에서 1로 내려가는 게 아닌, 1에서 num으로 점점 올라가는 아이디어가 떠올리기 어려웠던 것 같다 ㅠ_ㅠ