[백준/Python3] 27965번. N결수

서론

슬슬 1일 1백준을 시작하려는데, 올해의 목표는 파이썬으로 알고리즘 문제 풀기다.

C++이 편하고 쉬워서 자주 애용했지만, 아무래도 시간 단축엔 파이썬이 좋겠다는 판단.

그래서 오늘은 파이썬을 사용해서, 간단한 코테 재활 겸 실버 문제를 풀어본다.

문제

https://www.acmicpc.net/problem/27965

 

---

1. 첫 번째 풀이

사고 과정

N = 5, K = 7이 들어오면

N결수 = 12345 (1부터 N까지 이어붙이기)

답 = N결수 % K = 12345 % 7 = 4라는 아주 심플한 문제다.

 

파이썬이 문자열 다루기에 좋다고 소문이 자자해서, 한번 간단하게 코드를 만들어 돌려보았다.

 

코드

n, k = map(int, input().split())

gyeolsu = '1'
for i in range(2, n + 1):
    gyeolsu += str(i)

print(int(gyeolsu) % k)

 

결과

 

하지만 소문과 달리 날먹엔 실패했다.

---

2. 두 번째 풀이

사고 과정

그렇다면, 간단한 최적화가 필요하다는 뜻이렸다.

시간 제한은 1.5초니까 대강 150,000,000으로 잡으면 되겠지.

N이 10,000,000까지 되니까, 단순히 문자열 이어붙이는데만 최대 10,000,000개를 쓴다는 말이고, 그럼 큰 수의 나눗셈에서 문제가 좀 생겼나보다.

 

어떻게 하면 나머지는 동일하게 유지하되, 수의 크기는 줄일 수 있을까? 즉, 동일한 나머지를 갖는 적당히 작은 수를 어떻게 구할 수 있을까?

 

이론적으로, 수학적으로 접근하는 건 내 체질에 안 맞으니, 지금껏 쌓은 잡지식들을 총출동시켜보자.

 

가장 먼저 떠오른 건, 1부터 9까지, 각 수의 배수는 정해진 패턴이 있다는 것이었다.

예를 들어, 2는 홀수/짝수만 구분하면 되고, 5는 끝자리가 0인지, 5인지만 보면 된다.

4는 맨 끝의 두 자리만 보면 된다. 예를 들어 끝이 16으로 끝난다면 이건 4의 배수고, 78이라면 나머지는 2다. (76이 배수니까)

원리는 단순한데, 100이 4의 배수이기 때문에, 끝 두 자리를 제외한 나머지 숫자들은 어차피 날아가기 떄문이다.

 

8은 같은 원리로 끝 세자리만 보면 된다. 그런데 문제는 3, 9, 그리고 7이다.

3과 9는 자릿수를 모두 더하는 방법이 있는데, 그것도 상당히 오래 걸릴 뿐더러, 7이 답이 없다. 오죽하면 1000 - 7이 유명해졌겠나.

(번외로, 궁금해서 7의 배수 판정법을 찾아보니, 일의 자리를 분리해 b로, 나머지를 a로 뒀을 때, a - 2b 또는 3a + b가 7의 배수면 배수란다. 이게 무슨?)

 

안타깝게도, 이 방법을 쓸 순 없을 것 같다. 그럼 단순하게, 더하는 동시에 나머지 연산을 하면 안 될까?

 

N = 5, K = 7일 때

1 % 7 = 1

12 % 7 = 5

53 % 7 = 4

44 % 7 = 2

25 % 7 = 4

+) 12345 % 7 = 4

 

어찌저찌 답은 등장했다. 다른 경우에도 이게 성립할까?

 

N = 3, K = 11일 때

1 % 11 = 1

12 % 11 = 1

13 % 11 = 2

+) 123 * 11 = 2

 

이번에도 성립했다. 이게 맞는 방법인지 검증하려면, 수학적으로 모듈러 연산에 대해 알아봐야겠다.

 

강의를 들은지 꽤 지나서, 모듈러 연산에 관해 정보를 찾아봐야 했다. 구글링 대신 제미나이에게 물어봤다.

제미나이는 이 방법이 성립하는 이유를 모듈러 연산의 합동, 그리고 연산 보존 법칙으로 설명했다.

 

 

하지만 이 설명으론 충분하지 않다. 나는 이 원리를, 사칙 연산 수준의 논리로 설명되길 바란다. 그래서, 다시 질문했다.

 

이번엔, A를 mK + B로 대치했다. 이제야 완벽히 이해했다. A = mK + A 꼴로 둔다면, 당연히 그 나머지는 같을 것이다. 이때 mK + A = B로 표현하면, 합동 관계가 성립한다.

 

여기에, 블로그에서 찾은 아래의 법칙을 적용해본다.

https://developer-mac.tistory.com/84

 

123 % 7

= ( 120 + 3 ) % 7

= ( 120 % 7 + 3 % 7 ) % 7

= { ( 12 * 10 ) % 7 + 3 % 7 } % 7

= [ { ( 12 % 7 ) * 10 } % 7 + 3 % 7 ] % 7 (여기서, 12 % 7은 위 법칙이 아닌 합동으로 대치한 것이다.)

= { ( 5 * 10 ) % 7 + 3 % 7 } % 7

= ( 50 % 7 + 3 % 7 ) % 7

= 53 % 7

 

문자로 쓰면 뒤로가기 누를 것 같아 우선 숫자 예시로 써봤다. 문자 버전은 아래를 참고하자. (나라면 안 볼 것 같긴 하다. 가독성이 영...)

a = 기존 수, b = 뒤에 붙일 수, n = b의 자릿수, k = 나눌 수

( a * 10^n + b ) % k    // n은 b의 자릿수로, log_10 (b) + 1로 구할 수 있다. 여기선 편의상 n으로 적었다.

= ( a * 10^n ) % k + b % k ) % k

= { ( a * 10^n ) % k + b % k } % k

= [ { ( mk + a ) * 10^n } % k + b % k ] % k  (여기서, mk + a는 위 법칙이 아닌 합동으로 대치한 것이다. 간단히 a % k가 합동이다.)

= [ { ( a % 7 ) * 10^n } % k + b % k ] % k

= { ( a % 7 ) * 10^n ) + b } % k

그럼 이제 원리도 명쾌하게 이해됐겠다, 코드를 짜볼까?

코드

import math

n, k = map(int, input().split())

result = 1
for i in range(2, n + 1):
    result = result * pow(10, int(math.log10(i)) + 1) + i   # 뒤에 숫자 붙이기
    result %= k     # 미리 나머지 계산

print(result)

 

결과

 

하지만 N결수는 자비가 없었다. 이런.

---

3. 세번째 풀이

사고 과정

N은 최대 7자리 수까지 주어지는데, 그럼 pow에서 7제곱까지 연산 중이란 뜻이다. 그래봐야 10,000,000인데... 시간이 넘어가나...? 파이썬은 처음이라 잘 모르겠다. 어쨌든, 더 좋은 방법을 찾아야겠다.

 

결국 포기하고 c++로 통과한 뒤 정답 코드를 보고, 여기저기 자문을 구해봤는데...

아니 Pypy로 제출해야 빠르다고?

Python3로 제출해서 시간초과가 났던 거였다. 이게 무슨?

 

하는 김에 최적화도 조금 더해서, 코드를 손봤다. (매번 자릿수 계산하지 말고, 저장해뒀다가 늘어나는 시점에 늘리기)

코드

n, k = map(int, input().split())

result = 1
place = 10
for i in range(2, n + 1):
    if(i == place):
        place *= 10

    result = (result * place + i) % k

print(result)

 

결과

 

그리고 틀렸다. 응?

 

그래도 시간 초과가 아니니까 이젠 할 수 있겠지.

---

3. 마지막 풀이

사고 과정

높은 문제 진행률에서 실패했으니, 엣지 케이스가 있다는 거겠지.

 

살펴보니 for문에 문제가 있었다. n이 1일 경우, 나머지 연산을 하지 않고(!) 그대로 출력했다. ㅋㅋ....

그래서 1 1을 넣으면 0이 나와야 하는데, 그대로 1이 나왔다.

 

그래서 간단히 값만 좀 수정했다.

코드

n, k = map(int, input().split())

result = 1
place = 10
for i in range(2, n + 1):
    if(i == place):
        place *= 10

    result = (result * place + i) % k

print(result)

 

사실 참고한 코드랑 완전히 같아져서... 그닥 기분이 좋진 않다.

결과

 

아무튼 맞았으니 뭐... 파이썬 감 잡기 정도로 생각하자.

---

개선

사고 과정

 

코드

n, k = map(int, input().split())

result = 0
place = 10
for i in range(1, n + 1):
    if(i == place):
        place *= 10

    result = (result * place + i) % k

print(result)

 

결과

---

가장 효율적인 코드

https://www.acmicpc.net/source/101573024

내가 참고한 코드는 이 분의 코든데, 사실상 거의 모든 걸 배워갔다. 표절...이라면 표절이겠지만 C++ 유저의 파이썬 적응기로 너그럽게 봐주길... 아니 랭킹에서 내리게 해줘요 이럴 생각은 없었는데

 

https://www.acmicpc.net/source/99226330

그 외엔 이 분이 있는데

p *= 10**(i==p)

 

place를 올리는 과정이 흥미로웠다. bool 값으로 처리해서 if문을 생략한 스킬.

---

강평

파이썬이 아직 손에 덜 익어서 그런지 좀 어려웠고, 갈 길이 먼 것 같다. 개강 전에 파이썬 정돈 능수능란하게 다루게 노력해보자.