[알고리즘/문제] 백준 4375번: 1 (C++)

이번 문제는 내가 생각한 로직대로 풀리지 않아서 힘들었던 문제이다.

내가 원래 생각한 로직은 다음이다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<string>

using namespace std;

typedef long long ll;
ll b;
int a, cnt;
string s;

int main() {
    while (scanf("%d", &a) != EOF) {
        cnt = 1; b = 1;
        s = "1";
        while (b) {
            cnt++;
            s += "1";
            b = stoll(s) % a;
        }
        printf("%d\n", cnt);
    }

    return 0;
}

 

스트링에 1을 계속 붙여가며 나머지 연산을 했을 때 0이 되는 순간의 자리수를 출력하는 로직이다.

처음에 atoi로 했을때 샘플 테스트 케이스로 해도 시간이 엄청 오래 걸렸다.

그래서 stoi로 바꿔서 했는데, out of range가 발생했다.

시간 초과 문제는 해결했지만, 런타임 에러가 발생했다.

ll로도 커버가 불가능한 범위의 수가 들어오기 때문인 것 같다.

힘들게 짠 로직이 결국 쓸 수가 없을때의 기분이란...

 

결국 답 코드를 보며 강의를 들었다.

답 코드는 다음과 같았다.

#include<bits/stdc++.h>
using namespace std;  
typedef long long ll; 
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 == 0은 cnt가 n의 배수임을 의미한다.

(개인적으로 변수명을 cnt로 쓴 건 조금 헷갈린다.)

 

cnt = (cnt*10) +1;은 반복되면 뒤에 1을 계속 붙여나간다.

그런데 여기서 끝내버리면 수가 너무나도 커져서 ll로도 커버가 안되는 경우가 발생한다.

그래서 다음 줄인 cnt %= n;을 해준다.

 

여기서 한가지 알아야할 공식이 있다.

바로 모듈러 산술의 분배법칙이다.

(a ± b) % c = ((a % c) ± (b % c)) % c

(a x b) % c = ((a % c) x (b % c)) % c

위와 같은 공식이 성립한다고 한다.

 

나머지 연산을 수가 커지기 전에 미리 할 수 있다.

(((a*10+1) % c ) * 10 + 1 % c)... = (((a*10 + 1) * 10 + 1)...) %c

이 성립한다.

왜냐하면 1%c = 1 이기 때문이다.

 

 

[참고사이트]

https://sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)

 

[강의 사이트]