[백준] 15736번: 청기 백기 (C++)

15736번: 청기 백기

---

 

문제 )

소프트웨어융합대학 학생회에서 주최한 소융체전에서 청기 백기 뒤집기 게임이 한창이다. 소프트웨어학부, ICT융합학부가 번갈아가면서 게임을 진행하는 중이다. 게임의 규칙은 간단하다. 게임을 진행할 차례인 학부에서 출전한 선수들 N명이 존재한다. 학생들의 앞 탁자에는 N개의 깃발이 청색이 위로 백색이 아래로 보이도록 놓여있다. 이때 출전한 선수 중 첫 번째 선수는 N개의 깃발 중 1의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다. 다음 두 번째 선수는 N개의 깃발 중 2의 배수에 해당하는 번호의 깃발을 뒤집어 놓는다. i 번째 선수는 i의 배수에 해당하는 번호의 깃발을 뒤집고, N 번째 선수까지 진행하면 끝이 난다. 그렇다면 이 게임에서 N 명의 선수가 참가하고 N개의 깃발이 존재할 때, N 번째 선수까지 진행하여 완료된 상태에서 백색이 위로 놓여있는 깃발의 수가 몇 개인지 알아보자.

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

풀이)

 

풀이하는 과정.!

 

21억개. 6개 

0 = 청 1 = 백  0 0 0 0 0 0
1의 배수 =>   1 1 1 1 1 1 = 6개
2의 배수 =>   1 0 1 0 1 0 = 3개
3의 배수 =>   1 0 0 0 1 1 = 3개
4의 배수 =>   1 0 0 1 1 1 = 4개
5의 배수 =>   1 0 0 1 0 1 = 3개
6의 배수 =>   1 0 0 1 0 0 = 2개


백기 2개.6이라면?
1, 2, 3, 6 약수는 4개

1 1개 1
2 1개 1, 2
3 1개 1, 3
4 2개 1, 2, 4
5 3개 1, 5
6 2개 1, 2, 3, 6 => 정수론 문제이므로 관련해서 생각해보자.


1       1                             1개
2       1 0                          1개
3       1 0 0                       1개
4       1 0 0 1                    2개
5       1 0 0 1 0                 2개
6       1 0 0 1 0 0              2개
7       1 0 0 1 0 0 0           2개
8       1 0 0 1 0 0 0 0        2개
9       1 0 0 1 0 0 0 0 1     3개
=> 규칙 찾기 계속해서 이전에 만들어진 수열은 그대로 사용됨.


4의 약수 1, 2, 4 => 3개 V
0 > 1 > 0 > 1

5의 약수 1, 5 => 2개
0 > 1 > 0

6의 약수 1, 2, 3, 6 => 4개
0 > 1 > 0 > 1 > 0

7의 약수 1, 7 => 2개
0 > 1 > 0

8의 약수 1, 2, 4, 8 => 4개
0 > 1 > 0 > 1 > 0

9의 약수 => 1, 3, 9  => 3개 V
0 > 1 > 0 > 1

소수 / 약수가 짝수개
짝수 / 약수가 짝수개

제곱수일 경우 약수의 개수가 홀수개가 나오게 되고,
백기의 개수가 늘게된다.( 1, 4, 9, 16, 25 ....)

 

#include <iostream>
using namespace std;
 
int main() {
 
    int n, ans;
    cin >> n;
 
    ans = 0;
    for(int i = 1; i < n + 1; i++){
        // 제곱수가 n을 넘어가면 멈춤
        if(i * i > n) break;
        ans++;
    }
 
    cout << ans;
 
    return 0;
}

---

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

15736번: 청기 백기