[C++] 백준 6359번 - 만취한 상범 (다른 방법으로도 도전)

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.
그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.
구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.
방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

접근

와 이거 풀다가 다 던지고 싶었다..진심...

나름의 규칙을 찾다가 3번 정도 갈아 엎고 다시 생각했다..

결국 찾아낸 규칙은 n의 정답은 1부터100까지의 완전제곱수들중에 n이랑 같다면 그 완전제곱수가 정답이고 같은게 없다면 그나마 가장 큰 완전제곱수가 정답이다

진심 하나하나 그려가면서 찾음...(원래 이렇게 하는거일까...?)

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
using namespace std;

int main() {

    int num[10] = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 };
    int t;
    scanf("%d", &t);

    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n);

        int ans = -1;
        int cnt = 0;

        for (int j = 0; j <10; j++) {//9이면
            if (n >= num[j]) {
                ans = num[j];
            }

            cnt = sqrt(ans);
        }
        printf("%d\n", cnt);
    }
    return 0;
}

리뷰

문제에서 n은 100까지라고 했으므로 1부터 100까지 완전제곱수는 10개밖에 없다 그래서 미리 배열을 만들어뒀다.

그리고 for문으로 완전제곱수의 갯수인 10번만큼 돌면서

입력받은 n과 일치하거나 or 그나마 제일 큰 완전제곱수를 찾는다

그게 정답이다

근데 바로 출력하면 안된다 9라면 3이 정답이기 때문에 sqrt라는 함수를 써서 제곱근 값을 계산하면된다

 

근데 다 풀고 다른 사람들은 어떻게 풀었는지 보는데  dp방법으로 푸는게 정석...인가....? 

출처

6359번: 만취한 상범 (acmicpc.net)