알고리즘 - Python / 백준 - 1323번 : 숫자 연결하기

1323번: 숫자 연결하기 (acmicpc.net)

1323번: 숫자 연결하기

 

---

풀이

• 숫자를 연결하면서 k로 나누었을 때 나누어 떨어지는 수를 찾고 그때 몇번 이어붙여야 하는지 구하는 문제이다.
• 먼저 갈피를 잡아보기 위해 예제 케이스인 2 9를 실행하고 나오는 나머지들을 모두 확인하였다.
• 나열된 나머지들은 2 4 6 8 1 3 5 7 0 2 4 6 8 1 3 5 7 ... 로 확인한 결과, 패턴을 이루고 있었다.
• 2 9 의 경우는 2 4 6 8 1 3 5 7 0 이고 이때 처음으로 0이 나오는 9가 정답이 된다.
• 따라서 n % k 의 범위는 0 ~ k-1 일 것이고 , 그 사이에서 반복되는 패턴안에 0이 존재한다면 처음으로 0이 등장한 경우를 찾으면 되고 , 존재하지 않는다면 패턴이 확인된 그 즉시 -1 을 출력하면 된다.
• 나올 수 있는 나머지 경우에 대해 배열을 만들고 해당 나머지가 등장하면 1로 만들고 , 1인 배열에 한번 더 접근하면 패턴이라고 간주하고 -1 을 출력한다.
• 비둘기 집의 원리에 따라서 발생할 최대 연산의 횟수는 0~k-1까지의 나머지를 모두 찾은 후 중복되는 한가지를 찾는 경우이므로 k+1번 연산하게 될 것이다.
• 또한 일일이 앞이나 뒤에 숫자를 붙여 나누고 그 수의 나머지를 확인 하는 것은 시간이 오래 걸리므로 나머지 연산의 성질을 사용해야 한다.
• 앞이나 뒤쪽에 숫자를 붙이며 진행하는 모듈러 연산에 대해서 모듈러 연산의 성질을 통해 식을 정리하였고 , 이를 통해 연산 속도를 개선할 수 있다. 아래 필기 사진을 통해 간략하게 정리해 두었다.

 

 

비둘기집 원리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

비둘기집 원리 - 위키백과, 우리 모두의 백과사전

 

n,k = map(int , input().split(" "))
leng = (10**len(str(n))) % k
cnt = 1
mods = n%k
ori_mod = mods
check = [0 for i in range(100001)]
check[mods] = 1
while True:
    if mods == 0:
        print(cnt)
        break
    else:
        cnt += 1
        mods = (mods*leng + ori_mod)%k
        if check[mods] == 1:
            print(-1)
            break
        else:
            check[mods] = 1

---