[C++/C] 백준 | 1323번 숫자 연결하기 반례 + 풀이

1323번: 숫자 연결하기

비둘기집 원리를 사용하는 문제입니다.

k가 최대 10만이라는 점을 이용하여 k로 무언가를 나눈 나머지의 종류는 0~99999의 10만가지 라는 점을 이용합니다.

 

풀이 : N을 적어가며 K로 나누면서 나온 나머지의 값이 여태 나온 적이 있는지 배열로 저장해서 확인한 후, 똑같은 나머지가 나온 적이 있다면 숫자를 무한번 나눠도 loop에 빠지기 때문에 -1을 출력해주면 됩니다.

나머지가 0이 된다면 나누어 떨어진 것이기 때문에, 여태 N을 몇 번 썼는지 출력해주면 됩니다.

 

혹은 

N을 새로 적는 과정이 10만번 이상 반복될 경우 비둘기집 원리에 의해 겹치는 나머지가 1개 이상 발생하기 때문에, for문을 10만번 반복해보고 그래도 정답이 출력되지 않았을 경우 -1을 출력하는 방식으로 풀어도 가능합니다.

 

풀이 1

#include <stdio.h>
int main() {
    long long n, m, ans = 0;
    short arr[100001] = {};
    scanf("%lld %lld", &n, &m);
    int digit = 0, temp = n;
    while(n) {
        n /= 10;
        digit++;
    }
    n = temp;
    for(int i = 0; i <= 200000; i++) {
        while(n < m) { //while loop을 통해 N을 적어가는 과정
            for(int m = 0; m < digit; m++) {
                n *= 10;
            }
            ans++;
            n += temp;
        }
        n %= m;
        if(n == 0) { //나머지가 0인 경우 정답 출력
            printf("%lld", ans + 1);
            return 0;
        }
        else if(arr[n] == 0) { //처음 나온 나머지의 경우 나왔다고 체크해줍니다.
            arr[n]++;
        }
        else if(arr[n] > 0) { //여태 나온 나머지일 경우 -1 출력
            printf("-1");
            return 0;
        }
    }
}

풀이 2

#include <stdio.h>
int main() {
    long long n, m, ans = 0;
    scanf("%lld %lld", &n, &m);
    int digit = 0, temp = n;
    while(n) {
        n /= 10;
        digit++;
    }
    n = temp;
    for(int i = 0; i <= 100000; i++) {
        while(n < m) {
            for(int m = 0; m < digit; m++) {
                n *= 10;
            }
            ans++;
            n += temp;
        }
        n %= m;
        if(n == 0) {
            printf("%lld", ans + 1);
            return 0;
        }
    }
    printf("-1");
}

반례

10000000 9

Output : 9


10000000 99

Output : 99


10000000 9999

Output : 9999


10000000 99999

Output : 45


97859271 97517

Output : 20895


797859271 98710

Output : -1