Contents

0. 문제

문제

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 출력한다.

예제 입력 1

3
7
9901

예제 출력 1

3
6
12

1. 문제 이해

n을 저장한다. (1≤n≤10000)
1, 11, 111, 1111, 11111, … 을 n으로 나눠 나머지가 0인 값 중 최솟값을 찾는다.
int는 –2,147,483,648 ~ 2,147,483,647이고 long long은 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807이다.
int는 최대 10자리, long long은 19자리까지 가능하다.
20자리 이상이 필요하지 않을 것이라는 보장이 없다.

2. 제출

가. 시간 초과

// 백준 4375번: 1
#include <iostream>
using namespace std;

int n;
typedef long long ll;

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL); cout.tie(NULL);
    while(scanf("%d", &n) != EOF){
        ll cnt = 1, ret = 1;
        while(true){
            if(cnt % n == 0){
                printf("%lld\n", ret);
                break;
            }else{
                cnt = (cnt * 10) + 1;
                ret++;
            }
        }
    }
    return 0;
}
Code language: PHP (php)

while(scanf("%d", &n) != EOF){ : n의 개수를 알려주지 않았다.
printf("%lld\n", ret); : printf에서 long long 출력하는 방법.
EOF : EOF(End of File), 파일의 끝을 탐지하는 상수로서 파일의 끝에 도달했을 때 언제나 특별한 값을 반환하도록 함.

일단 생각나는대로 풀어보았다.

시간도 초과하고 long long보다 큰 20 자릿수도 계산할 수 없다. → 입력값 9999 계산 불가.

아마 큰 수를 직접 나누는 방식으로는 문제를 풀 수 없을 것 같다.

나. 수정

이전에 배운 모듈러 연산을 활용하면 long long 혹은 int를 넘어서는 일도 발생하지 않고 시간도 줄일 수 있다.

[알고리즘] 1629번: 곱셈

0. 문제 1629번: 곱셈 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입력 1 예제 출력 1 1. 문제 이해 A B C = 10 11 12라면… A B C = 7 8 9 라면 … 2. 제출 가. 시간 초과 시간을 줄이기 위해서는 b를 줄여야 한다. 4 3 5 1 9 다섯 숫자가 반복된다. b를 … 더 읽기

23년 11월 16일 추가

나눠야 하는 수가 …

정해져 있을때 → 재귀함수를 통한 모듈러 연산
변화할 때 → while문을 통한 모듈러 연산

cnt(i) % n = (cnt(i-1) * 10 + 1) % n
cnt(i) % n = ((cnt(i-1) * 10) % n + (1 % n)) % n
cnt(i) % n = (((cnt(i-1) % n) * (10 % n)) % n + (1 % n)) % n
// -> 나머지 값은 나머지의 나머지, 나머지의 나머지의 나머지, ...와 같다.
Code language: JavaScript (javascript)

cnt % n 과 같이 모듈러 연산을 수행할 뿐이라면 굳이 cnt 값을 그래로 저장하기보단 모듈러 연산의 결괏값(cnt % n = 나머지)만 저장해도 된다.

cnt에 cnt %= n하면 기본적으로 그 크기가 n을 넘어설 수 없다.

cnt가 int를 넘어서는 일도 발생하지 않고 계산 시간도 줄일 수 있다.

// 백준 4375번: 1
#include <iostream>
using namespace std;

int n;

int main(){
    while(scanf("%d", &n) != EOF){
        int cnt = 1, ret = 1;
        while(true){
            if(cnt % n == 0){
                printf("%d\n", ret);
                break;
            }else{
                cnt = (cnt * 10) + 1;
                cnt %= n;   //추가
                ret++;
            }
        }
    }
    return 0;
}
Code language: PHP (php)

cnt %= n : 모듈러 연산. cnt의 나머지는 cnt의 나머지의 나머지와 같다.

출처 : https://velog.io/@donghak/scanf-반환값-EOF

[알고리즘] 4375번: 1