취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15736번 문제인 청기 백기이다.
문제는 아래 링크를 확인하자.

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

깃발 뒤집기를 직접 시뮬레이션하기에는 N의 제한이 너무 크다. 따라서 다른 방법을 생각해야한다.

어떤 깃발 하나의 위치를 k라 할 때, 이 깃발이 뒤집힌 횟수는 k의 약수의 개수와 같다. 그 이유는 각 약수번째 학생이 나와서 깃발을 뒤집힐 때 k번째 깃발은 뒤집히고, 그렇지 않은 경우 k번째 깃발은 뒤집히지 않기 때문이다.

결국 깃발 뒤집기가 끝난 후 흰색이 위로 오는 깃발의 개수는 N 이하의 "약수가 홀수개인 수"의 개수랑 같다는 것을 알 수 있다.

한편, 약수가 홀수개인 수는 완전제곱수밖에 없다는 사실은 잘 알려져있다. (보이기도 어렵지 않다.) 이를 이용해 문제를 간단히 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	int ans = 1;
	while (ans * ans <= N) ans++;

	cout << ans - 1;
}