백준 4375 1 c++ [컴공과고씨]

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

4375번: 1

이 문제는 시간초과로 못풀어서 어떤식으로 풀어야하는지 처음으로 답을 참고를 했던 문제이다. 그래서 나중에 한번 더 복습이 필요할 것 같다. 아무튼 어떤식으로 풀었고 시간초과가 났으면 어떤식의 해결방법이 옳았는지 보겠다.

처음 푼 방법은 1, 11, 111, 1111이렇게 직접 n으로 나누어가면서 1의 개수를 늘려주어 나머지가 0인것을 찾으면 될거라고 생각했다. 하지만 이렇게 풀면 시간 초과가 걸리기 때문에 나머지 연산 공식을 써주어야한다.

이 문제는 나머지 연산 공식만 알면 쉽게 풀지만 모르면 못푸는 그런 문제이다.

 

처음 푼 코드

#include <iostream>
using namespace std;
int main(){
    long long n;
    long long num = 1;
    int cnt = 1;
    while(cin >> n){
        num = 1;
        cnt = 1;
        while(1){
            num = num % n;
            if(num == 0){
                break;
            }
            num = (num * 10) + 1;
            cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
} // 시간초과
 

이런식으로 1을 늘려갔더니 시간초과가 났다. 이유는 1의 개수가 엄청 많아지면 long long에서도 담지 못할때까지 가기 때문에 그렇다고한다. 그리고 연산속도도 차이가 나기때문이다. 그래서 나는 여기서 막혀서 고민 끝에 검색을 해보았다.

나머지 연산을 이용해야한다고 되어있어서 공식만 딱 가져와서 풀어보았다.

나머지 연산의 공식은 (A+B)%C = (A%C + B%C)%C 라고 한다.

그렇다면 이것을 이용해서 저 위의 코드를 바꾸어 주면된다.

나머지 연산 공식을 보면 오른쪽 수 보다 왼쪽수가 훨씬 작아지는 것을 볼 수 있다. 그렇기 때문에 무작정 1을 늘려가면 나머지를 구하는 것 보다 연산 속도가 빠르다는 것을 볼 수 있다.  자 그럼 위 공식을 적용한다면

num*10을 A로 놓고 1을 B로 놓는다면 15번째 줄을 num = num*10%n + 1%n 이것으로 바꾸어주면 다음 반복문 때

11번째 코드 줄에서 %n을 전체적으로 해주기 때문에 결국 (A+B)%C = (A%C + B%C)%C이 성립하게 된다.

이렇게하면 시간초과 문제를 해결 할 수 있다.

 

전체 코드

#include <iostream>
using namespace std;
int main(){
    long long n;
    long long num = 1;
    int cnt = 1;
    while(cin >> n){
        num = 1;
        cnt = 1;
        while(1){
            num = num % n;
            if(num == 0){
                break;
            }
            num = (num * 10)%n + 1%n; //나머지 연산 공식 사용 
            cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}
 

사용 알고리즘 : 나머지 연산

 

 

yea!