BOJ - 파스칼(2986)

실버3 : 수학 문제이다.

생각

일단 코드가 처음보는 거라 유심히 보았다. 결국 이런 것을 묻는 문제였다.

가장 큰 약수가 뒤에서 부터 몇번째에 나오니?

그렇다면 가장 큰 약수를 구해야 하는데, 가장 큰 약수는 사실 $\sqrt{n}$ 까지만 조사해도 풀 수 있다. 모든 수는 약수로 1을 가지므로 1을 초기값으로 두고, $\sqrt{n}$까지 루프를 돌며 가장 큰 약수를 구한 뒤, 그 값까지 오는 count 개수를 출력하면 된다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int main(){
    int n, divisor = 1;
    cin >> n;
    for (int i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            divisor = n/i;
            break;
        }
    }
    cout << n-divisor << '\n';
}

Reference

• 백준(2986번) - 파스칼