(C++) - 백준(BOJ) 1975: Number Game

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

1975번: Number Game

진법 계산을 해보는 수학 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

테스트 케이스의 개수 t, 십진법 수 n을 선언한 후 t만큼 n을 입력해줍니다. 테스트 케이스는 100만, 1000진법까지 살펴봐야하므로 1억의 loop를 돕니다. 아슬아슬한 시간제한 1초를 통과하기 위해 #define fastio를 적용해줍니다.

 

📔 풀이과정

n을 입력후 i=2 ~ 1000까지 n을 i진법으로 바꿨을 때 뒤부터 연속된 0의 개수를 반환하는 함수 f를 실행합니다. while loop를 도는데 나눈 나머지가 1이상이면 지역변수 cnt를 ++, 0이 아니라면 break해줍니다. 뒤 부터 연속된 0의 개수를 세주면 되기 때문입니다.

반환된 값을 ans에 더해줍니다.

📔 정답출력

ans를 출력해줍니다. 

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int t, n;

int f(int n, int i) {
    int cnt = 0;
    while(n) {
        if(n % i == 0) cnt++;
        else break;
        n /= i;
    }
    return cnt;
}

int main(){
    fastio;
    cin >> t;
    while(t--){
        cin >> n;
        int ans = 0;
        for(int i = 2; i <= 1000; i++) ans += f(n, i);
        cout << ans << '\n';
    }
}