백준 6359번 만취한 상범

문제 링크입니다: https://www.acmicpc.net/problem/6359

다이나믹 프로그래밍 주제에 있던 문제였지만 메모이제이션을 통해 풀지는 않았습니다.

동적계획법으로 푸는 것보다 제가 푼 방법이 좀 더 쉬운 방법인 것 같습니다.

/*

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다.

각 방에는 벌점을 많이 받은 학생들이 구금되어있다.

그러던 어느날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다.

게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다.

그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다.

같은 방식으로 n번의 라운드를 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

 

int N;

int cell[MAX]; //열려있으면 1, 닫혀있으면 0

 

void prisonBreak(int num)

{

        for (int i = num; i <= N; i += num)

        {

               int previous = cell[i];

               cell[i] = 1 - previous; //1 -> 0, 0 -> 1

        }

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               if (N < 5 || N >= MAX)

                       exit(-1);

 

               memset(cell, 0, sizeof(cell));

               for (int i = 1; i <= N; i++)

                       prisonBreak(i);

 

               int result = 0;

               for (int i = 1; i <= N; i++)

                       if (cell[i]) //열려있다면

                              result++;

 

               cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

*이 문제는 사실 범위 내의 제곱수의 갯수를 구하는 문제입니다.