[백준 BOJ] 4375번 - 1 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

code.plus 문제집 : 코딩 테스트 준비 - 기초 | 수학

4375번: 1 | 문제 바로가기

문제풀이 (2022-02-01 TUE 💻)

🤔 사담

벌써 2월이라니... 말도 안돼...
시간 왜이렇게 빨리 흐르는지 모르겠다 ㅠㅠ
설 연휴라서 하루 쉴까.. 하는 마음도 살짝 들었지만
2월의 첫 날인 만큼! 마음을 새로 다잡고 오늘도 1일 1코딩 완료 👊
대신 좀 가볍게 실버 문제 풀어봤는데
문제는 짧았지만 생각보다 의미있는 부분들이 몇 가지 있어서 기록해본다

⭐ 풀이의 핵심 + 🚨 간과 또는 실수한 부분

👉 결론부터 말하자면 모듈러 연산이 핵심이었다
1, 11, 111, 1111, ... 이렇게 숫자를 계속해서 키워나가면
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)도 넘어간다

while문을 한 번 돌 때마다
1 다음 11, 11 다음 111, ...을 바로 넘겨주는 것이 아니라
1로만 이루어진 해당 숫자의 크기가 너무 커지지 않도록
mod N 연산을 해주고 넘어가는 것이다

참고할 모듈러 연산 공식

• x mod n = (x mod n) mod n
• (a + b) mod n = (a mod n + b mod n) mod n
• (a * b) mod n = (a mod n * b mod n) mod n
  
  ex)
  1 % 7 = 1
  11 % 7 = (1*10+1)%7 = (1%7*10+1)%7 = (1*10+1)%7 = 4 이므로
  111 % 7 = (11*10+1)%7 = (11%7*10+1)%7 = (4*10+1)%7 = 6
  1111 % 7 = (111*10+1)%7 = (111%7*10+1)%7 = (6*10+1)%7 = 5
  ... 와 같기 때문에 1 다음에 11 대신 4를, 11 다음에 111 대신 6을 넘겨줄 수 있다

🚨 처음에는 long long 범위 내에서 계산 가능하다고 착각하여
나는 모듈러 연산을 쓰지 않고
1, 11, 111, ... 을 담는 변수(아래 코드에서 num)만 long long으로 선언해주었는데
시간초과가 났고
스스로 답을 얻지 못해.. 결국 구글링을 통해 알아냈다.. 😥
이산수학, 컴퓨터보안 수업에서 지겹게 모듈러 연습문제 풀었던 것 같은데
생각해보니 코테 문제 풀면서 직접 적용해본 적은 없는 것 같다..

🔥 숫자가 너무 커지는 것을 방지하기 위해 모듈러 연산을 활용할 수 있음을 기억하자 !

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

👉 추가로 이 부분에 대해서는 아래와 같이 처리해주면 된다
cin, cout 같은 경우는 scanf, printf보다 속도가 느린 문제가 있는데
std::ios::sync_with_stdio(false);
를 설정해주면 해당 문제가 해결된다고 한다
(단, 해당 코드 추가 시 C 스타일 및 C++ 스타일 입출력의 혼용을 허용하지 않고
C 스타일의 입출력을 무시하게 되므로 scanf, printf는 쓰면 안 된다)
코테에 따라 이를 허용하지 않을 수도 있다는 얘기를 들어서
나는 그냥 scanf, printf를 주로 쓰는 편이다

// cin
using namespace std;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
// 1.
while (cin >> N) { ... }
// 또는 2. 
while (!cin.eof()) {...}

// scanf (EOF: End Of File)
int N;
while (scanf("%d", &N) != EOF) { ... }

🚨 덧붙여,
출력 포맷을 "%d\n" 이 아니라 "%d" 로 지정했다가 틀렸습니다 가 떴다
어이 없게 틀리지 않도록.. 입출력 형식 잘 확인하기.. 💧

🔽 코드 (C++)

#include <iostream>
using namespace std;

int main() {
    /*
    HINT) 모듈러 연산
    x mod n = (x mod n) mod n
    (a + b) mod n = (a mod n + b mod n) mod n
    Line #20의 연산을 포함하지 않으면 시간 초과 발생
    */
 
    int N;
    int digit;
    while (scanf("%d", &N) != EOF) {
        digit = 1;
        int num = 1;
        while(1) {
            if (num % N == 0) { break; }
            digit++;
            num = num * 10 + 1;
            num %= N;
        }
        printf("%d\n", digit);
    }
    
    return 0;
}