[알고스팟] 웨브바짐

ZIMBABWE

클릭시 이동합니다!

웨브바짐

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • ZIMBABWE
  • 2000ms
  • 65536kb
  • 842
  • 354 (42%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러!

계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. 예를 들어 계란 한 개에 35억 웨브바짐 달러라고 하면, 3이 쓰인 판 한 개, 5가 쓰인 판 한 개, 0이 쓰인 판 여덟 개를 빈칸에 순서대로 끼우는 것이죠.

무가베 마트에서 아르바이트를 하는 종욱이는 어느 날 곤란한 손님을 맞았습니다. 이 손님은 아까 사 갔던 계란을 환불하겠다고 돌아왔는데, 영수증을 잃어버린데다 계란을 얼마에 샀는지를 기억하지도 못한다고 하는군요. 계란 값은 그 사이 한 번 또 올랐기 때문에 광고판에 적힌 가격은 이미 바뀐 뒤입니다. 다행히 종욱이는 두 가지를 기억합니다.

• 마지막에 계란 가격이 올랐을 때, 종욱이는 광고판에 꽂힌 플라스틱 판의 순서만 바꿨습니다. 다른 플라스틱 판을 가져오거나 있던 플라스틱 판을 뺄 일은 없었다는 것이죠.
• 마지막 계란 가격을 보면서 '와 이거면 정확히 사탕 m개를 살 수 있구나' 라고 생각했습니다. 따라서 마지막 계란 가격은 m의 배수였습니다. (사탕 가격도 이미 올랐기 때문에 이걸 가지고 계란 가격을 계산할 수는 없습니다)

지금 계란 가격 e와 m이 주어질 때 가능한 이전 계란 가격이 몇 가지나 있는지 계산하는 프로그램을 작성하세요. 이전 계란 가격은 e 보다 항상 작아야 합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 그 후 c줄에 각각 2개의 자연수 e와 m (1 <= e <= 10^14, 2 <= m <= 20)이 주어집니다. 현재 계란 가격은 0으로 시작하지 않지만, 이전 계란 가격은 0으로 시작할 수 있습니다.

출력

각 테스트 케이스마다 한 줄에 가능한 가격의 수를 1,000,000,007 로 나눈 나머지를 출력하세요.

예제 입력

4
321 3
123 3
422 2
12738173912 7 

예제 출력

5
0
2
11033

어떻게 풀까?

가장 중요한 것은 '수를 어떻게 만들 것인가?' 를 정하는 것입니다.

각 자릿수의 순열을 이용해서 만든다고 생각해봅시다.

예제 입력의 422를 예로 들겠습니다.

그렇다면, 인덱스 순서대로

0 1 2 = 422

0 2 1 = 422

1 0 2 = 242

1 2 0 = 224

2 0 1 = 242

2 1 0 = 224

실제로 만들어지는 수는 422, 242, 224 세가지 이지만, 순열을 이용해서 만들면 6가지의 경우의 수가 생기기 때문에 중복해서 세는 경우가 생깁니다.

이를 위해서는 우선 e의 각 자릿수를 정렬해서 만든 배열을 이용하면 됩니다.

그림으로 설명하겠습니다.

입력을 432242 라고 하겠습니다.

위 그림처럼, 정렬을 하고 나면 각 자리에서 가장 앞에있는 수만을 다음 수로 선택하면 됩니다!

가장 앞에있는 수를 알아내는 방법은

1. 앞에 아무것도 없다 (i = 0)

2. 앞의 인덱스랑 값이 다르다.

입니다.

그리고, 맨 앞의 2를 선택했다고 가정합시다.

위 그림처럼, 만약 맨 앞의 2가 이미 쓰였다면, 가장 앞에 있는 2는 그 뒤의 2가 될 것입니다.

이렇게, 맨 앞의 수를 갱신해주면서 선택 가능한 수를 선택하도록 하면, 중복되는 수는 나오지 않을 것 입니다!

이제 수를 하나하나 만드는 방법을 정했으니, 중복되는 부분을 통해 메모이제이션을 적용하는 단게로 가봅시다.

문제에서 요구하는 것은 다음과 같습니다.

1. 항상 원래 수보다 작아야 한다.

2. 만들어진 가격이 m의 배수여야한다.

우선, 항상 원래의 수보다 작기 위해서는 어떻게 해야하는지 생각해 봅시다.

입력은 213이라고 가정하겠습니다.

위 그림처럼, 만약 선택했던 수들이 원래 수보다 작지 않다면 원래 수보다 큰 값을 선택해서는 안됩니다.

만약, 원래 수보다 작은것이 확정되어있다면, 선택할 수 있는 수는 나머지 모든 수와 같아집니다.

원래 수보다 작으려면, 가장 왼쪽에 있는 자리가 한 번이라도 원래 수보다 작으면 되는 것입니다! 

따라서, 원래보다 작은 것을 선택한 적이 있었는지를 함수의 인자로 추가해주고, 메모이제이션에도 이를 알기 위한 공간을 만듭시다.

다음으로는 만들어진 가격이 m의 배수여야한다는 부분입니다.

이를 위해서는 우선 나눗셈이 어떻게 계산되었는지를 다시 한 번 돌이켜볼 필요가 있습니다.

가장 중요한 것은 위 부분입니다! 처음에 1과 3을 선택한 다음 이 수를 6으로 나눈 나머지 1뒤에 2를 붙여서 계산하는 것을 볼 수 있습니다!

만약 13245가 31245였으면 어떨까요?

13 % 6 = 1이고 31 % 6 = 1이기 때문에 나머지 진행 상황은 똑같을 것 입니다!

즉, 선택한 인덱스와 그 나머지가 같다면, 그 뒤에 부분은 중복 계산을 한다는 것을 알 수 있습니다!!

인덱스를 선택한다는 것은 인덱스마다 true와 false를 이용한다는 것으로 생각할 수 있습니다.

즉, 비트 마스킹을 하는 것이 편하다는 것입니다!

메모이제이션을 저장하는 배열은 따라서,

memoi[나머지][선택한 인덱스들][2(원래 수 보다 더 작을 경우와 아닐 경우)] 를 이용하면 구할 수 있습니다!

참고로, memoi에는 선택한 인덱스들이 원래 수보다 작은경우 or 아닐 경우, 나머지가 X라고 할 경우에 나누어 떨어지는 개수가 들어갑니다.

코드

#pragma once
#include<cstdio>
#include<cstring>
 
using namespace std;
 
int div[20][1 << 15][2] , len, m;
//e : 입력, digit : 정렬된 e
char e[16], digit[16], temp[16];
const int MOD = 1000000007;
 
int getLen()
{
    int i;
    for (i = 0; e[i]; i++);
    return i;
}
 
void mergeSort(int left, int m, int right)
{
    int l = left, r = m + 1, k = left;
 
    while (l <= m && r <= right)
    {
        if (digit[l] < digit[r]) temp[k++] = digit[l++];
        else temp[k++] = digit[r++];
    }
 
    while (l <= m) temp[k++] = digit[l++];
    while (r <= right) temp[k++] = digit[r++];
 
    for (int i = left; i <= right; i++) digit[i] = temp[i];
}
 
void merge(int left, int right)
{
    if (left < right)
    {
        int m = (left + right) / 2;
        merge(left, m);
        merge(m + 1, right);
        mergeSort(left, m, right);
    }
}
 
int setDiv(int index, int mod, int selected, bool lower)
{
    if(index == len){
        return lower && (mod == 0);
    }
 
    int &ret = div[mod][selected][lower];
    if (ret != -1) return ret;
 
    ret = 0;
 
    for (int next = 0; next < len; next++) {
        if (selected & (1 << next)) continue; //이미 선택된 인덱스 금지
        if (next != 0 && digit[next - 1] == digit[next] && ((selected & (1 << (next-1))) == 0)) continue; // 중복 선택 금지
        if (!lower && e[index] < digit[next]) continue; // 이미 작지 않은 상태인데 더 큰거 선택 금지
 
        int ns = selected | (1 << next);
        int nl = lower || (e[index] > digit[next]);
        int nm = (mod * 10 + digit[next] - '0') % m;
 
        ret += setDiv(index + 1, nm, ns, nl);
        ret %= MOD;
    }
 
    return ret;
}
 
int main()
{
    int tc;
    scanf("%d\n", &tc);
 
    while (tc--)
    {
        scanf("%s %d\n", e, &m);
 
        memset(div, -1, sizeof(div));
 
        len = getLen();
        memcpy(digit, e, sizeof(e));
 
        merge(0, len -1);
        int res = setDiv(0, 0, 0, 0);
        printf("%d\n", res);
    }
    return 0;
}

여담

이번 문제는 결국 풀지 못했습니다!

앞의 수들을 나머지로만 저장하면 된다는 사실을 깨닫지 못했기 때문에 메모이제이션의 메모리가 너무너무 커져버렸어요.

DP의 매력이 바로 저것처럼 사소한걸 알기만 한다면 문제는 금방 풀린다는 것 같습니다.

물론, 사소한걸 놓친다면 풀 수 없게 되죠...

시간 복잡도는 어떻게 될까요?

e의 자리수가 n이라고 할 떄,

부분 문제의 개수가 m * 2^n이고, 함수에서 n번 반복하는 반복문이 있기때문에

이 됩니다.