[6359] 만취한 상범

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

 

 

문제를 읽고 천천히 시뮬레이션 돌리다보니, 한 숫자에 대해 홀수 번 지나가면 문이 열리고, 짝수 번 지나가면 문이 닫힌다는 것을 알았다.

몇 번 지나가는지를 어떻게 판별할까 생각했을때, 2번, 3번은 반드시 문이 닫히게 되었고,

4번부터는 1번,2번,4번이 지나기 때문에문이 열렸다.

이때 약수의 개수가 홀수개면 문이 열리고, 약수가 짝수개면 문이 닫힌다는 것을 알았다.

 

100번까지 확인한다고 했을때 각 숫자의 약수의 개수를 알아야했기 때문에 for문을 두개 써야했다.

첫번째 for문은 숫자 하나하나가 문이 닫혔는지 열렸는지 확인하는 for문이고,

두번째 for문은 약수의 개수를 확인하기 위한 for문이다.

(테스트 케이스 포함한다면 하면 3개이다.)

 

약수의 개수를 확인하는 알고리즘 중 시간복잡도가 최대한 낮은 로직을 발견해 함수로 만들었다.

코드는 다음과 같다.

 

#include<iostream> 

using namespace std;

int T;
int n;
int answer;
int cnt;

int factor_odd(int a) 
{
	cnt = 0;

	for (int i = 1; i * i <= a; i++)
	{
		if (i * i == a)
		{
			cnt++;
		}
		else if (a % i == 0)
		{
			cnt += 2;
		}
	}
//	cout << "cnt:" << cnt << "\n";
	if (cnt&1) return 1;
	else return 0;
}

int  main() {
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		answer = 0;
		cin >> n;
		for (int j = 1; j <= n; j++)
		{
			answer += factor_odd(j);
		}
		
		cout << answer << "\n";
	}
	return 0;
}

 

 

참고한 글

https://dnf-lover.tistory.com/entry/C-%EC%95%BD%EC%88%98%EB%A5%BC-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%95%BD%EC%88%98%EB%A5%BC-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%8B%A4%EC%96%91%ED%95%9C-%EB%B0%A9%EB%B2%95%EA%B3%BC-%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4