[Week 10] PASS486 self review - Yunhyunjo

[Yunhyunjo]

self review

1. 해결 시도 과정

단순히 약수 개수 구하는 코드를 짜서 숫자를 세고 출력을 하면 될 것이라고 생각했습니다.

2. 아이디어

j * j가 i 보다 작을 때 까지만 돌려 약수의 개수를 세주고 입력받은 n과 같다면 카운트해주었습니다.

3. 코드 설명

#include <iostream>

using namespace std;

int Count(int n, int x, int y);

int main(void) {

	int c, n, lo, hi;

	cin >> c;

	while (c--) {
		cin >> n >> lo >> hi;
		cout << Count(n, lo, hi) << "\n";
	}

}

int Count(int n, int x, int y) {
	int cnt = 0, num = 0;
	for (int i = y; i >= x; i--) {
		for (int j = 1; j * j  <= i; j++){
			if (i % j == 0) {
				if (i / j == j)
					num++;
				else
					num += 2;
			}
		}
	}

	for (int i = x; i <= y; i++) {
		if (num == n)
			cnt++;
	}

	return cnt;
}

for문을 입력받은 범위만큼만 돌려 약수의 개수를 세어주었고, j * j <= i일때 까지만 돌려서 값이 나누어 떨어는가를 체크해서 개수를 세어주었습니다. 몫과 나눈 값이 같다면 1을 더하고 아니라면 2를 더해주는 식으로 약수의 개수를 구해주었습니다.

4. 막힌 점 및 개선 사항

수가 커지면서 약수의 개수를 구하는 이중 for문에서 시간초과가 나는것 같습니다. 약수의 개수를 구하는 다른 방법을 좀 더 생각해 보아야 할 것 같습니다.