[백준] 4375번: 1 (java, python, 나머지 연산)

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

4375번: 1

---

🗒 코드

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int num = 0;

            for (int i = 1;i <= n; i++) {
                num = (num * 10 + 1) % n;

                if (num == 0) {
                    System.out.println(i);
                    break;
                }
            }
        }
        sc.close();
    }
}

---

python

while True:
    try:
        n = int(input())
    except Exception:
        break
    num = 0
    i = 1

    while True:
        num = num * 10 + 1
        num %= n
        if num == 0:
            print(i)
            break
        i += 1

 

 

---

🤔 후기

사실...진짜 문제 조차도 이해가 안됐다.

1로만 이루어진 n의 배수를 찾는 것이 대체 무슨 말이란 말이냐.

멍청해보이지만 친구들이 2~3번 정도 인내심을 갖고 가르쳐줘서 겨우 이해할 수 있었다.

1로 이루어진 배수들, 즉 1, 11, 111을 n으로 나누었을 때 나머지가 0이 되는 경우를 찾는 문제였다.

첫 테스트케이스에서 n=3일 때 결과가 3인 것은 111 % 3 = 0 (몫 = 37) 이므로, 111, 즉 1이 3개다 라는 뜻이었다.

두번째 테스트케이스에서 n=7일 때 결과가 6인 것은 111111 % 7 = 0 (몫 = 15873) 이므로, 111111, 즉 1이 6개다 라는 뜻이었다.

 

문제는 이해했으나, 코드가 계속 타임아웃이 되었다.

1을 하나씩 증가시키면서 n의 나머지를 구해보고, 만약 나누어 떨어지면 return하는 코드는 옳은 방법이 아니었다.

 

해법은 교수님이 전에 올려주신 문제에 있었다.

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

10430번: 나머지

단순한 print 문제여서 이걸 왜 내셨지? 했는데, 힌트는 여기에 있었다. 나머지 연산을 사용하는 것이었다.

 

$11 = 10 * 1 + 1$로 표현할 수 있다.

나머지 연산은 이를 사용하는 것인데, 조건은 다음과 같다. (백준 10430번에 나와있는 내용과 같다.)

 

1. $a = b  \%  n$ 과 $b  = c \% n$은 $a = c \% n$ 을 의미한다.
2. $[(a \% n) + (b \% n)] \% n = (a + b) \% n $
3. $[(a \% n) - (b \% n)] \% n = (a - b) \% n $
4. $[(a \% n) * (b \% n)] \% n = (a * b) \% n $

num = (num * 10 + 1) % n

이 코드와 유사하지 않은가?

교수님이 허투루 과제를 내주신게 아니었다...

---