문제 풀이 과정을 공유하고자 한다.
문제 출처

1. 문제설명

  • x, y, n이 주어진다.
  • 1 <= x <= y <= 1,000,000
  • 사용 연산
    • x에 n을 더한다.
    • x에 2를 곱한다.
    • x에 3을 곱한다.
  • 연산을 최소로 사용하여 x를 y로 만들자.



2. 알고리즘 설계

  • 연산을 최소로 사용하여 == BFS
  • ++DP를 이용하는 방법도 있다.



3. 로직

  • BFS
    • queue에서 꺼냈을 때 y랑 같아지면 그 때의 weight를 리턴
    • q.empty()까지 못 찾으면 -1 리턴
  • DP
    • memo[i*2] = min(memo[i*2], min[i] + 1)
    • 위와 같이 숫자와 연산자만 바꿔서 갱신한다.
    • x<=i<=y의 만큼 for문을 실행한다.


4. 전체 코드

#include <queue>

using namespace std;
using pii = pair<int, int>;

using namespace std;

const int INF = 1000001;
bool visited[INF] = { false, };

int bfs(int x, int y, int n) {
    queue<pii> q;
    q.push({ x, 0 });

    while (!q.empty()) {
        pii cur = q.front();
        int cx = cur.first;
        q.pop();

        if (cx == y)
            return cur.second;

        if (cx * 2 <= y && !visited[cx * 2]) {
            q.push({ cx * 2, cur.second + 1 });
            visited[cx * 2] = true;
        }
        if (cx * 3 <= y && !visited[cx * 3]) {
            q.push({ cx * 3, cur.second + 1 });
            visited[cx * 3] = true;
        }
        if (cx + n <= y && !visited[cx + n]) {
            q.push({ cx + n, cur.second + 1 });
            visited[cx + n] = true;
        }
    }

    return -1;
}

int memo[INF];
int DP(int x, int y, int n) {
    fill_n(memo, INF, INF);
    memo[x] = 0;

    for (int i = x; i <= y; i++) {
        if (i * 2 <= y) memo[i * 2] = min(memo[i * 2], memo[i] + 1);
        if (i * 3 <= y) memo[i * 3] = min(memo[i * 3], memo[i] + 1);
        if (i + n <= y) memo[i + n] = min(memo[i + n], memo[i] + 1);
    }

    return (memo[y] == INF) ? -1 : memo[y];
}

int solution(int x, int y, int n) {
    return DP(x, y, n);
    return bfs(x, y, n);
}


5. 소감

  • 일반적인 BFS처럼 next 좌표가 0보다 작아지는 경우를 신경쓰지 않아도 된다.
  • x, n 모두 1 이상의 값이기 때문이다.
  • 사실 이 문제는 오래 전 00소프트 코딩테스트에서 유사한 문제가 출제되었었다.
    • 그 때는 못 풀었는데… 지금은..! 좀 더 노력하자