[백준 1463번] 1로 만들기

문제 주소는 여기로

아까 merge sort 문제 풀고 나서

가볍게 도전해 볼 문제로 고른 이번 문제...

그러지 말았어야 했어요.

 

입력받은 숫자를

1. 3으로 나누어 떨어진다면 3으로 나누거나

2. 2로 나누어 떨어진다면 2로 나누거나

3. 1을 뺀다.

 

위 세 과정 중 하나를 반복하여 결과적으로 숫자를 1로 만들고,

그러기까지 필요한 총 연산 수의 최솟값을 출력하는 문제입니다.

 

무수한 틀렸습니다의 요청이...

되게 단순한 문제인 줄 알았는데 그게 아니더라구요.

3 또는 2로 나누어 떨어질 때도, 1을 빼는 쪽이 결과적으로 더 연산이 적게 필요할 수도 있어요.

예를 들어 10은 10-5-4-2-1, 총 연산수 4번이지만

10-9-3-1, 즉 1을 빼는 쪽으로 시작하면 총 연산수가 3번입니다.

 

늘 그렇듯 잘 모를 때는 백준의 질문 검색을 이용합니다...

알고리즘 분류는 다이나믹 프로그래밍, 그 중에서도 BFS (Breadth First Search; 너비 우선 탐색) 으로 해결하는 문제라고 합니다.

 

이론을 분명 배웠을텐데 기억이 안 나서 바로 공부했어요.

설명 글은 여기서.

BFS를 이용한 최소 거리 찾기는 지금도 이해를 잘 못했어요... ㅠㅠ

 

문제 풀면서 가장 많은 도움을 받은 질문글은 아래와 같습니다.

1. 댓글에 반례

2. BFS 방법으로 푸신 분 코드 참고

 

이후로 약 3~4시간 머리 싸매고 고민하였으나 답은 나오지 않았고...

결국 이 블로그에서 내용을 참고했어요.

 

결과적으로 제가 생각했던 depth를 구분하여 푸는 방법은 queue를 두 개 사용하셨더라구요.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int input;
    cin >> input;
    
    bool visited[input+1];
    for (int i = 0; i <= input; i++)
        visited[i] = false;
    queue<int> before;
    queue<int> after;
    before.push(input);
    
    int count = 0;
   
    while (!before.empty())
    {
        int num = before.front();
        before.pop();
        
        if (num == 1)
        {
            cout << count << '\n';
            break;
        }
        
        if (num > 1 && !visited[num])
        {
            visited[num] = true;
            if (num % 3 == 0)
                after.push(num/3);
            if (num % 2 == 0)
                after.push(num/2);
            after.push(num-1);
        }
        if(before.empty())
        {
            before = after;
            while (!after.empty())
                after.pop();
            count++;
        }
        
    }
    
    return 0;
}

블로그 원 작성자분은 Java로 작성하셨는데, 저는 C++로 베껴왔습니다.

 

내용은 어렴풋이 이해가 되긴 하는데 제가 작성한 코드가 아니다 보니 조금 더 시도를 해 봐야 할 것 같아요.

일단 글은 올려놓고 나중에 추가 보충 설명 더 하는걸로...