C++ SWEA 16800. 구구단 걷기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYaf9W8afyMDFAQ9

SW Expert Academy

풀이

N의 약수를 2개씩 짝 지어서 (1,1)에서 가장 적게 떨어져있는 것을 찾아서 반환!

for (long long i = 1; i * i <= a; i++) { // 약수구하기

    if (a % i == 0) {
        v.push_back(i);
        if (i != a / i) v.push_back(a / i); // 100일때 10 *10 두 번 들어가는거 방지
    }
}

약수구하는 코드는 구글링해서 찾아따,,, 기억해두자 유용하게 쓰일듯!?

 

그리고 만약 홀수개일때는

ex) 1,5,25 일때는 (1,25) , (5,5) 이렇게 가운데 있는 것은 두번 사용해서 짝지어주어야한다.

범위가 크기 때문에 long long타입 쓰는거 잊지말기,,,

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	
	int t_c = 0;
	cin >> t_c; // test_case
	

	for (int i = 0; i < t_c; i++) {

		long long a;
		cin >> a;
		vector <long long> v;
		for (long long i = 1; i * i <= a; i++) { // 약수구하기

			if (a % i == 0) {
				v.push_back(i);
				if (i != a / i) v.push_back(a / i); // 100일때 10 *10 두 번 들어가는거 방지
			}
		}
		sort(v.begin(), v.end());

		long long ans = 1000000000000; // 최솟값

		for (long long i = 0; i < v.size() / 2; i++) {
			ans = min(ans, v[i] + v[v.size() - 1-i] - 2);
		}

		// 홀수 개일때, 숫자 두번 사용
		if (v.size() % 2 != 0) {
			ans = min(ans, v[v.size() / 2] * 2 - 2);
		}

		cout<<"#"<<i+1<<" "<<ans<<endl;
	}
	return 0;
}