[알고리즘] 4375번: 1

0. 문제

 

4375번: 1

 

문제

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

입력

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

출력

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

예제 입력 1

3
7
9901

예제 출력 1

3
6
12

 

---

1. 문제 이해

 

1. n을 저장한다. (1≤n≤10000)
2. 1, 11, 111, 1111, 11111, … 을 n으로 나눠 나머지가 0인 값 중 최솟값을 찾는다.
3. 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이다.
4. int는 최대 10자리, long long은 19자리까지 가능하다.
5. 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;
}

• 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번: 곱셈

 

• 23년 11월 16일 추가

나눠야 하는 수가 ...

1) 정해져 있을때  → 재귀함수를 통한 모듈러 연산
2) 변화할 때 → 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
// -> 나머지 값은 나머지의 나머지, 나머지의 나머지의 나머지, ...와 같다.

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;
}

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

 

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

---