1-O

내 풀이(http://boj.kr/4f28d15fd33c43739ee9e7262e1041c6) - 틀림

공유 소스 보기

---

1-O

오늘은 1-O 백준 4375번 문제를 풀어보겠습니다.

그 전에 여러분 배수란 뭘까요? 예를 들어서 4가 2의 배수가 된다라는 걸 코드로 어떻게 표현하죠?

이렇게 표현할 수가 있겠죠.

그러니까 4라는 수가 2의 배수라는 거는 '4 % 2를 모듈러 연산한 값이 0이면, 4는 2의 배수구나' 라는 거를 파악할 수가 있죠.

자 이 문제는 1로만 이루어진 수 중에서 n의 배수, 그리고 가장 작은 것의 자릿수를 구하는 문제죠?

그러니까 뭐냐면 1, 1, 1, 1, 1, 1 이렇게 쭉쭉쭉 만들어가지고 결국에 n으로 모듈러 연산을 한 값이 0임을 통해서 배수인 거를 확인합니다.

그리고 그때의 자릿수를 뽑아내는 문제인데 어떻게 해야 될까요?

예를 들어서 111 모듈러 연산 3은 0이죠. 그래서 n이 3일 때, 자릿수가 3이니까 정답이 3이 나오는 겁니다.

이렇게 해서 예시까지 이해를 해봤고, 자, 그러면 풀이 방법에 대해서 얘기를 해보도록 할게요.

자, 처음에 들은 생각은 이런 걸 생각할 수가 있겠죠?

이렇게 먼저 1들을 만들어 놓고 모듈런 연산 n을 한다라고 할 수가 있겠죠.

'어? 선생님 9901 같은 경우는 출력이 12니까 long long으로 할 수 있지 않나요? 12자리는 1000억이니까 long long으로 커버 되잖아요! 그러니까 우리 그냥 만들어 놓고 해봅시다' 라고 생각할 수가 있겠죠.

그럼 정말 되는지 안 되는지 확인해보면 되잖아요.

이게 그렇게 만든 코드 입니다. 그런데 만약에 이걸 제출하게 되면 시간 초과가 날 겁니다.

이 코드를 돌려봐서 9999 라는 숫자를 넣고 cnt를 출력하도록 디버깅을 해보면,

이렇게 계속 돌아가는 걸 볼 수 있습니다. 그러니까 지금 보시면 long long으로 선언했어도 long long에 벗어나는 숫자가 만들어지고 있다라는 겁니다.

자 그러면 어떻게 해야 될까요? 바로 정수론의 모듈러 연산 법칙을 사용하면 됩니다.

모듈러 연산 법칙은 이렇습니다.

이게 가지는 의미는 뭐냐면, 우리가 이렇게 플러스 곱하기로 이루어진 수들은 끝에 가서 모듈러 연산을 하지 않고 그 전 단계에서 이렇게 모듈러 현상을 일일이 해줘도, 그 끝에 가서 모듈러 연산을 한 결과값과 동일하다는 의미입니다.

자, 우리가 앞서서 구축한 코드 잠깐 볼게요.

코드를 보면,

이 cnt를 끝에 가서 마지막에 모듈러 연산 n한 것과 같잖아요.

근데 이거는 사실 이 중간 단계에서 모듈러 연산 n을 하는 것과 동일한 효과를 가진다라는 거에요. 왜? 곱하기와 플러스로 이루어진 식이니까요.

그래서 끝에 가서 모듈러 연산 n이 아니라, 이 전 단계에서 모듈러 연산을 계속해도 괜찮다 라는 겁니다. 그러면 그거를 적용해서 코드를 바꿔보도록 할게요.

바로 이것만 추가를 하시면 됩니다. 그러니까 마지막에 가서 모듈러 연산을 하는 게 아니라, cnt를 만들 때마다 중간중간 모듈러 연산 n을 해도 똑같은 값이 나온다라는 거예요.

그리고 입력이 몇 번 주어지는지 안 나와있는 경우에는 이렇게 작성하시면 됩니다.

그리고 ret은 자릿수를 체킹하기 위한 변수입니다.