120번째 죄수

감옥에 120명의 죄수가 있다. 간수는 복도를 120번 동안 다음 조건에 지나간다.

  • 처음에 문은 모두 닫혀 있다.
  • N번째 지나갈 때에는 N의 배수인 문들이 열려 있으면 닫고, 닫혀 있으면 연다.
  • 마지막에 문이 열려 있으면 그 방의 죄수는 석방이다.

과연 몇 명의 죄수가 석방될까?

배수 규칙 감옥
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

36개의 풀이가 있습니다. 1 / 4 Page

k 번 방의 문이 열리거나 닫히는 것은 간수가 k의 약수번째 지나갈 때 일어납니다.

따라서 최초에 모든 문은 닫혀있으므로, 홀수번 여닫음이 일어나면 그 문은 최종적으로 열린 상태가 되어 죄수가 석방될 수 있습니다.

자연수 a, b, c 에서 a * b = c 일 때 a, b 는 둘 다 c 의 약수이므로 약수의 개수가 홀수개가 되는 수는 거듭제곱수 밖에 없습니다.

120까지의 거듭제곱수는 1~10의 각각의 제곱수인 10개가 있습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
public class prisoner
{

    public static void main(String[] args) 
    {
        int count = 0;
        boolean[] prison = new boolean[121];

        for(boolean i  : prison) i = false;

        for(int guard = 1; guard < prison.length; guard ++)
        {
            for(int door = 0; door < prison.length; door ++)
            {
                if(door % guard == 0)
                {
                    int temp = door;

                    if(prison[temp] == false) prison[temp] = true;
                    else if(prison[temp] == true) prison[temp] = false;
                }
            }

        }

        for(int i = 0; i < prison.length; i ++)
        {
            if(prison[i]== true) 
            {
                count++;
                System.out.println(i+"번째 방 오픈");
            }
        }

        System.out.println(count);
    }

}

이거맞아요? 10명탈출하고 n^2번 방에 있는 사람이 탈출하는걸로 나오던데...

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

PHP입니다.

$rooms = array_fill(1,120, 0);

for($i=1; $i<=120; $i++) {
    foreach($rooms as $num => $value) {
        if($num%$i==0) {
            $rooms[$num] = ($value==0)?1:0;
        }
    }
}

echo array_sum($rooms);
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

p (1..120).count {|n| n**2 <= 120 } #=> 10

or

free = ->n,f=1,cnt=0 { n>=f ? free[n,f+1,cnt+(n%f>0?0:1)] : cnt.odd? }
cnt_frees = ->n { (1..n).count &free }

Test

expect( [1,4,9,16,25,36,49,64,81,100].all? &free ).to eq true
expect( [2,3,8,18,120].all? &free ).to eq false
expect( cnt_frees[120] ).to eq 10

Output

p cnt_frees[120] #=> 10
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

c로 해봤습니다

#include<stdio.h>

#define CLOSE 0
#define OPEN 1

int main(void)
{
    int num_free=0; //석방되는 죄수 수
    int index, count; //index는 배열의 인덱스, count는 몇번째 왔다갔다 하는지
    int prison_arr[120] = { CLOSE, }; //감옥 상태 배열

    for (count = 1; count <= 120; count++)
    {
        for (index = 0; index < sizeof(prison_arr) / sizeof(prison_arr[0]); index++)
        {
            if ((index + 1) % count == 0)
            {
                switch (prison_arr[index])
                {
                case OPEN:
                    prison_arr[index] = CLOSE;
                    break;
                case CLOSE:
                    prison_arr[index] = OPEN;
                    break;
                default:
                    break;
                }
            }
        }
    }

    for (index = 0; index < sizeof(prison_arr) / sizeof(prison_arr[0]); index++)
    {
        if (prison_arr[index] == OPEN)
            num_free++;
    }

    printf("%d \n", num_free);


    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

머리로 풀기

약수 개수가 홀수 개인 숫자만 세면 된다. 이는 곧 제곱수를 의미하고, 11의 제곱이 121이니까, 10명.

Python 3

gates = [False for i in range(121)]

for x in range(1, 121):
        j = 1
        while j*x <= 120:
                gates[j*x] = not gates[j*x]
                j = j + 1

print(gates.count(True)) # Output : 10
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

c언어로 짯습니다.

#include <stdio.h>
#include <stdbool.h>


void main(){

    bool open[121] = { false, };
    int i,  k; 
    int num=0; //석방되는 죄수의 수


    for (i = 1; i < 121; i++){

        for (k = 1;; k++){
            if (i*k >120) break;

            if (open[i*k] == true)
                open[i*k] = false;

            else
                open[i*k] = true;


        }

    }


    printf("석방 되는 죄수  : ");
    for (i = 1; i<121; i++){

        if (open[i] == true){
            printf("%d   ",  i);
            num++;

        }
    }


    printf("석방 되는 죄수의 수  : ");
    printf("%d", num); // 죄수의 수 print


}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

철저하게 순서대로 동작을 짜보니 답이 나오네요. 코드는 너무 지저분 하긴 한데.. ^^ 거듭제곱이 해라는 것은 정말 신선한 수학적 접근인 것 같습니다.(To. 룰루랄라)

# -*- coding: utf-8 -*-
"""
Created on Fri Aug 19 20:48:04 2016

@author: giljae7.lee
"""
import numpy as np

# set doors : 0 close, 1 open
door = np.zeros((120, 1))

for no_loop in range(1, 120):
    for gansu in range(1, 120):
        for n_pos in range(1, 120):
            remain = ((float)(n_pos)/gansu) - (int)(n_pos/gansu)
            if remain == 0:
                if door[n_pos] == 0:
                    door[n_pos] = 1
                else:
                    door[n_pos] = 0
    for gansu in range(120, 1):
        for n_pos in range(1, 120):
            remain = ((float)(n_pos)/gansu) - (int)(n_pos/gansu)
            if remain == 0:
                if door[n_pos] == 0:
                    door[n_pos] = 1
                else:
                    door[n_pos] = 0

print ("The free prisoners are ... ")
for n_pos in range(1, 120):
    if door[n_pos] == 1:
        print(n_pos)


The free prisoners are ... 1 4 9 16 25 36 49 64 81 100

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def prisoner(n) :
  a = [ 0 for i in range(n)]

  for i in range(1,n+1) :
    for j in filter( lambda x : x % i == 0 , range(1,n+1 ) ) :
      a[j-1] = ( a[j-1]==0 ) and 1 or 0
  print sum(a)

prisioner(120)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

허접한 풀이

#include<stdio.h>

void main(void) {
    int prison[121]; // 0 close, 1 open
    for(int i = 1 ;(i < 121); i++ ) {
        prison[i] = 0;
    }

    for(int i = 1 ;(i < 121); i++ ) {
        int j = 1;
        while((j*i) < 121) {

            if(prison[j*i] == 0) 
                prison[j*i] = 1;
            else
                prison[j*i] = 0;
            j++;
        }
    }

    int count = 0;
    for(int i = 1 ;(i < 121); i++ ) {

        if(prison[i] == 1){
            printf(" %d  %d  %d \n   ", i, prison[i] , count);
            count++;
        }
    }

    printf(" 답 : %d \n ", count);

}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

배수 x 1
규칙 x 1
감옥 x 1

언어별 풀이 현황
전 체 x 36
기 타 x 6
java x 8
php x 2
ruby x 1
python x 14
r x 1
cs x 1
cpp x 3