[백준 15736] 청기 백기 - python

💡문제 분석 요약

소프트웨어융합대학 학생회에서 주최한 소융체전에서 청기 백기 뒤집기 게임이 한창이다. 소프트웨어학부, ICT융합학부가 번갈아가면서 게임을 진행하는 중이다. 게임의 규칙은 간단하다. 게임을 진행할 차례인 학부에서 출전한 선수들 N명이 존재한다. 학생들의 앞 탁자에는 N개의 깃발이 청색이 위로 백색이 아래로 보이도록 놓여있다.

이때 출전한 선수 중 첫 번째 선수는 N개의 깃발 중 1의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다.

다음 두 번째 선수는 N개의 깃발 중 2의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다.

i 번째 선수는 i의 배수에 해당하는 번호의 깃발을 뒤집고, N 번째 선수까지 진행하면 끝이 난다.

그렇다면 이 게임에서 N 명의 선수가 참가하고 N개의 깃발이 존재할 때, N 번째 선수까지 진행하여 완료된 상태에서 백색이 위로 놓여있는 깃발의 수가 몇 개인지 알아보자.

입력

첫 번째 줄에 출전한 학생의 수이자, 깃발의 개수인 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

첫 번째 줄에 N 번째 선수까지 진행한 후의 상태의 깃발 중 백색이 위로 놓여있는 깃발의 수를 출력한다.

💡알고리즘 설계

0: 청색, 1: 백색

1. 0으로 채워진 N 크기의 배열이 존재한다.
2. 1부터 N번째 선수까지 아래 행위를 반복한다.
   1. i번째 선수는 i의 배수에 해당하는 번호의 깃발을 뒤집는다.
3. 백색이 위로 놓여 있는 깃발의 수를 출력한다.

⇒시간 복잡도 초과

0: 청색, 1: 백색으로 두고 직접 그려 봤다.

N=1 → 0 → 1 백색 1개

N=2 → 00→11→10

N=3 → 000 → 111→101→100

N=4 → 0000→1111→1010→1000→1001

N=5 → 00000→11111→10101→10001→10011→10010

N=6 → 000000→111111→101010→100011→100111→100101→100100

N=7 → 0000000→1111111→1010101→1000111→1001111→1001011→1001000

7번째 수는 1,7번째에 바뀜→1001000

N=8→8번째 수는 1,2,4,8번째에 바뀜→10010000

N=9→9번째 수는 1,3,9번째에 바뀜→100100001

N=10→10번째 수는 1,2,5,10번째에 바뀜→1001000010

i번째 깃발은 해당 배수 차례가 지나가면 바뀌지 않고, 않는다.

i번째 깃발은 약수의 개수가 홀수면 청색(0), 짝수면 백색(1)이다.

4, 9와 같이 제곱수일 때 약수의 개수가 홀수이다.

💡코드

N = int(input())

flag = [ 0 for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(i, N+1, i):
        flag[j]= not flag[j]

print(sum(flag))

완전탐색으로 시간이 오래 걸린다.

N = int(input())

i=1
squre=i*i

while squre<=N:
	i+=1
	squre=i*i

print(i-1)

제곱수가 N을 초과하지 않을 때 까지 반복한 후 출력했다.

💡시간복잡도

N이 21억이라 완전 탐색을 하면 안된다.