[C언어]백준(BOJ) 4375 - '1'

 

#문제 분석

문제 링크 | https://www.acmicpc.net/problem/4375

4375번: 1

 

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

 

KEY 1 | '각 자릿수가 모두 1로만 이루어진' -> ex) 1, 11, 111, 1111, 11111

KEY 2 | 'n의 배수' -> n으로 나누었을 때 나머지가 0이다. 

---

 

#기본 개념

크게 이 문제를 풀기 위해 알아둬야 할 기본 개념을 2가지 라고 생각했습니다. 

 

첫 번째는 모듈러의 연산

두 번째는 EOF

 

1) 모듈러의 연산

쉬운 표현으로는 나머지 연산, 나머지 값 이렇게 부를 수도 있을 것 같습니다. 

정확하게는 A mod B = R (A는 피제수, B는 제수, R은 나머지) 라는 식을 사용할 수 있습니다. 프로그래밍 언어에서는 %로 모듈러 연산을 나타냅니다.  

 

예시)

11 mod 7 = 4 

: 몫은 다들 아시다시피 1 이고 나머지는 4죠.  

 

이러한 모듈러의 연산이라는 개념에서 오늘의 문제를 풀기 위해 또 중요한 하나의 개념이 있습니다.

바로 모듈러 연산의 분배법칙 입니다. 

 

1) (A+B) % n = {(A%n) + (B%n)} % n
2) (A-B) % n = {(A%n) - (B%n)} % n
3) (A*B) % n = {(A%n) * (B%n)} % n

 

직접적으로 해당 공식을 아예 대입해서도 문제를 풀 수 있을 것 같습니다만 저는 분배법칙의 개념을 머리에 박아둔 채로 '큰 수를 모듈러 연산할 때 미리 작은 수에 대해 모듈러 연산을 진행해도 결과는 같다' 라는 생각으로 문제에 접근했습니다.   

2) EOF

EOF는 End Of File 의 약자이자, 파일의 끝을 표현하는 상수로 값은 -1로 지정되어 있습니다. 주로 파일을 열고난 후 파일의 데이터의 끝을 알아볼 때 EOF를 사용하지만, 입력될 값이 몇 개나 주어질지 모를 때 C언어에서 사용하기도 합니다. 

 

while (scanf("%d", &n) != EOF)               

 

바로 이런 식으로 사용이 됩니다.

 

직관적으로 보면 파일의 끝까지 입력을 계속해서 받겠다는 조건으로 즉, 종료 조건이 명확하지 않을 때 유용하게 사용할 수 있는 코드입니다.   

 

키보드에서도 강제적으로 EOF 값을 반환할 수 있는데 그 값은 Ctrl + Z(Windows) / Ctrl + D(Linux) 로, 운영체제에 따라 다른 것을 염두에 주시면 좋을 것 같습니다. 

 

 

#코드

 

 

해당 문제의 규칙성을 찾기 위해 메모했던 이미지를 캡쳐해보았습니다.

각 자릿수가 1인 숫자를 만들어내기 위한 하나의 식을 정리 했고(왼), 이를 문제의 예시 답안(입력:7 / 출력:6) 에 대입해보았습니다.(오) 

 

결론을 내보자면 정리한 식에 n을 모듈러 연산하여 저장하고 계속 식에 대입하여 0이 될 때까지 모듈러 연산 하면 된다는 것이었습니다. 

 

코드는 아래와 같습니다. 

#include<stdio.h>

int main() {
    int test_num = 0; // 나누려는 n
    int ans; // while문 1번이 자릿수와 같고, 가장 작은 수의 자릿수를 출력하기 위해 설정
    long long a = 0; // 나머지 값을 저장해 둘 변수
    int flag; // 모듈러 연산의 반복을 조절하기 위해 설정

while(scanf("%d", &test_num) != EOF) {
       
       flag = 0;
       ans = 0;

        while(flag == 0) {
            a = a * 10 + 1;
            a %= test_num;
            ++ans;
            if (a == 0) {
                printf("%d\n", ans);
                flag = 1;
                break;
            }
        }
}

    return 0;

}