[백준/c++] 15736번: 청기 백기

문제 링크 - https://www.acmicpc.net/problem/15736

🌱 문제

🌱 풀이

• 처음엔 딱히 생각이 안나서 ,문제에서 말하는 그대로 for문을 돌려보았다.
• 처음에 청색이니까 백색이 되는 것들은 홀수번 뒤집힌 것이므로, 1부터 N까지 수 중에 약수가 홀수개인 것들을 카운트 해 주었다.

//약수의 갯수 리턴하는 함수
int func(int n)
{

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
            cnt++;
    }
    return cnt;
    }
    

• 이렇게 약수갯수를 리턴해주는 함수를 작성하고, main문에서 1부터 N까지 돌면서 func(i)값이 홀수인 것들을 카운트 했다.
• 당연히 시간초과가 났다. 시간제한은 1초인데 약 1억번 돌면 1초고, 입력값 N의 범위는 21억이니까.
• 약수가 홀수란 뜻은 제곱수일때에만 가능한 결과이다.
• 그러므로 1부터 N까지 수 들중에 제곱수인 것들만 카운트해 주어서 정답을 풀었다.

🌱 코드

// 15736번: 청기 백기
#include <iostream>
using namespace std;
int n;

    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        int answer = 0;
        cin >> n;

        // 1부터 n까지 수 중에서 제곱수의 갯수 카운트
        for (int i = 1; i * i <= n; i++)
        {
            answer++;
        }

        cout << answer << "\n";
    }
    //약수 갯수가 홀수인것만 최종적으로 백색임.
    //약수 갯수 홀수라는건 제곱수 라는뜻.