[ 백준 6359 ] 만취한 상범 (C++)

백준의 만취한 상범(6359) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제에서 방문이 열려있는지 아닌지를 관리하기 위해서 DP[] 1차원 배열을 사용하였다.

   DP[a] = 1 의 의미는 a번 방문이 열려있습니다 를 의미하고, DP[a] = 0 의 의미는 a번 방문이 닫혀있습니다를 의미한다.

   풀이과정은 생각보다 단순하다.

   1라운드부터 총 N라운드까지 진행하는데, 해당 라운드의 배수인 문들의 상태를 확인하고 0이면 1로, 1이면 0으로

   만들어 주면 된다.

  

   사실 위의 풀이가 끝이다. 이 후, 모든 방의 상태를 다 더해주면, 열려있는 방의 갯수가 나오게 된다.

   왜냐하면, 열려있는 방은 1로, 닫혀있는 방은 0으로 표시되어 있기 때문에, 방의 상태를 다 더해주면 열려 있는 방의 갯수

   만큼만 1이 더해지기 때문이다.

   정확한 풀이는 위의 풀이가 끝이다. 하지만, 문제를 풀던 중 꼼수 풀이를 발견했다. 처음에 예제입력으로 주어진

   5와 10을 풀어놓고, 열려있는 방들을 한번 다 확인해보았다.

   확인해보니 5일 때는 { 1, 4 } 로 2개가 열려있었고

   10일 때는 { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 } 으로 100개가 열려있었다.

   즉, 최종적으로 열려있는 방은 N보다 작거나 같은 제곱수들이었다.

   뭐 이런 방법으로도 풀 수 있다는 걸 읽어만 보자.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 101
using namespace std;
 
int N;
int DP[MAX];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    // Dynamic Programming 풀이
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j * i <= N; j++)
        {
            if (DP[i * j] == 0) DP[i * j] = 1;
            else DP[i * j] = 0;
        }
    }
 
    int Sum = 0;
    for (int i = 1; i <= N; i++)
    {
        Sum = Sum + DP[i];
    }
    cout << Sum << endl;
    
    // 야매풀이
    //int Cnt = 0;
    //for (int i = 1; i <= N; i++)
    //{
    //    if (i * i <= N) Cnt++;
    //}
    //cout << Cnt << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}