백준 15736번: 청기 백기

백준 15736번: 청기 백기

15736번: 청기 백기

청기와 백기가 양면으로 있는 깃발이 놓여져있고, 선수들이 n번째 차례일때 n의 배수에 해당하는 깃발들을 뒤집는 게임을 하고 있다. 청기를 뒤집을 경우 백기, 백기를 뒤집을 경우 청기 간단히 시뮬레이션으로 풀 수 있을거라 생각할지도 모르겠지만 이 문제의 범위는 N이 21억까지 갈 수 있다는 것이다. 단순 시뮬레이션으로하면 최대 21초가 걸릴수있는 끔찍한 상황이 벌어질지도 모른다. 그러니 주어진 시간내에 풀어야하는 것이면 규칙을 찾는게 시간을 최대한 줄일 수 있다.

나는 우선 1의 배수를 다 뒤집어놓은 백기 상태로 시작해서 2의 배수를 뒤집고 3의 배수를 뒤집고... 를 메모장에다가 적어서 상태를 봤다. 

 

백백백백백,백백백백백 = 1의 배수

백청백청백,청백청백청 = 2의 배수

백청청청백,백백청청청 = 3의 배수

백청청백백,백백백청청 = 4의 배수

백청청백청,백백백청백 = 5의 배수

백청청백청,청백백청백 = 6의 배수

백청청백청,청청백청백 = 7의 배수

백청청백청,청청청청백 = 8의 배수

백청청백청,청청청백백 = 9의 배수

백청청백청,청청청백청 = 10의 배수

 

백과 백 사이에 청이 오는 것을 볼 수 있었고, i의 배수일 때 i의 이전값들은 변하지 않는 것을 확인했다. 백과 백사이에 청이 오는것 2의 배수로 오는 것인지 i의 제곱수로 오는것인지 정확하게 확인하기 위하여 16까지 상태를 더 적었고 그 결과 i의 제곱수마다 백이 오는 것을 알았다. 그러면 답을 찾는 것은 간단하다. 어떤 숫자가 입력되었을 때, i의 제곱이 그 숫자를 넘지 않는 최대값이 정답인 것이다.

 

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    long long n;
    cin >> n;
    long long value;
    for(long long i = 1; pow(i, 2) <= n; i++){
        value = i;
    }
    cout << value;
    return 0;
}