[SWEA] 10806. 수 만들기

date

Jul 27, 2023

slug

making-number

author

status

Public

문제

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXTC4piqD_IDFASe&categoryId=AXTC4piqD_IDFASe&categoryType=CODE&problemTitle=수+만들기&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

풀이

이 문제는

X에 D를 더하거나

D에 어떤 수를 곱해서

X를 K로 만들어야 하는 문제입니다.

D는 어떤 수를 계속 곱해주거나 그대로이기 때문에 어떤 수를 곱해준 D의 배수가 K가 안된다면 D에 곱해주면 안됩니다. 문제 예시 입력중 두번째 케이스를 봅시다.

A = [3], X = 0, D = 1, K = 16입니다.

D = 1, K = 16

D = 1, K = 15 → 여기서 D에 3을 곱해주지 않은 이유는 3을 곱해버리면 16이라는 수를 만들 수 없습니다.

D = 3, K = 15 → 여기서 D에 3을 곱해준 이유는 15가 3의 배수이기 때문에 5번 더하면 15를 만들어 줄 수 있기 때문입니다. (그리고 곱해주는게 무조건 이득입니다.)

D = 3, K = 12 → 여기서 D에 3을 곱해주지 않은 이유는 3을 곱해버리면 9가 되는데 9를 여러번 더해 15라는 수를 만들 수 없기 때문입니다. 따라서 D를 빼주었습니다 (15 - 3)

D = 3, K = 9 → 여기서 D에 3을 곱해주지 않은 이유는 9를 여러번 더해 12라는 수를 만들 수 없기 떄문입니다.

D = 9, K = 9 → 여기서 D에 3을 곱해준 이유는 9가 9의 배수이기 때문입니다.

따라서 총 4번 빼주었기 때문에 답은 4가 됩니다.

여기서 한가지 중요한 아이디어가 있습니다. 바로,

D = 3, K = 15

D = 1, K = 5

두 경우를 같은걸로 취급할 수 있다는 것입니다.

15 - 3 - 3 - 3 - 3 - 3 = 0 은

5 - 1 - 1 - 1 - 1 - 1 = 0과 같은거랑 동치입니다.

그럼 D = 3, K = 15를 D = 1, K = 5로 보고 이후 과정을 다시 봅시다.

D = 1, K = 5

D = 1, K = 3 → 여기서 D에 3을 곱해주지 않은 이유는 3을 곱해버리면 5라는 수를 만들 수 없습니다. 그리고 K를 1 빼기보다 3의 배수가 되게 빼주는게 이득입니다. 따라서 K - 2 = 3을 해줍니다.

D = 3, K = 3

이렇게 해도 총 4번 빼주었기 때문에 답은 똑같이 4가 됩니다.

이를 이용해 K에서 0으로 가는 최단거리 문제로 볼 수 있습니다. D에 배열 A의 원소를 곱한다는 것을 역으로 K에 배열 A의 원소를 나눈다 라고 생각할 수 있습니다. 만약 배열 A의 원소에 있는 수와 나눠 떨어진다면 비용은 들지 않게 되고, 나눠 떨어지지 않는다면 나눠 떨어지는 수로 만들고 그 만큼의 비용을 더해주면 됩니다.

그냥 단순히 배열로 거리를 확인하면 메모리가 굉장히 커지기 때문에(10^9라서) unordered_map을 이용해 확인해주었습니다.

코드


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;

int tc;

void go() {
    int n, k, arr[11];
    scanf("%d", &n);
    unordered_map<int, int> mp;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &k);
    pq.push({0, k});
    mp[k] = 0;

    while (!pq.empty()) {
        int cost = pq.top().first, cur = pq.top().second;
        pq.pop();
        if (cur == 0) {
            printf("%d\n", cost);
            return;
        }
        for (int i = 0; i < n; i++) {
            if ((cur % arr[i]) == 0) {
                if (mp.find(cur/arr[i]) != mp.end() and mp[cur/arr[i]] <= cost) continue;
                pq.push({cost, cur / arr[i]});
                mp[cur/arr[i]] = cost;
            } else if (cur - (cur % arr[i]) >= 0) {
                if (mp.find(cur-(cur%arr[i])) != mp.end() and mp[cur-(cur%arr[i])] <= cost + (cur % arr[i])) {
                    continue;
                }
                pq.push({cost + (cur % arr[i]), cur - (cur % arr[i])});
                mp[cur-(cur%arr[i])] = cost + (cur % arr[i]);
            }
        }
    }
}


int main() {
    scanf("%d", &tc);
    for(int i = 1; i <= tc; i++) {
        printf("#%d ", i);
        go();
    }
}