109개의 풀이가 있습니다.
room = [-1] * 120
for i in range(1, 120+1):
for j in range(1, 120+1):
if j % i == 0:
room[j-1] *= -1
print(room.count(1))
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번 방에 있는 사람이 탈출하는걸로 나오던데...
public class Main {
public static void main(String[] args) {
int cnt = 0 ;
boolean door[] = new boolean[199];
for(int i = 1 ; i<=120 ; i++){
for(int j=1 ; j<=120 ; j++){
if( j%i == 0 ){
door[j] = !door[j];
}
}
}
for(boolean item : door){
if(item){
cnt ++;
}
}
System.out.println(" 총 " + cnt +"명");
}
}
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);
}
def criminal(num):
door = [ 0 for i in range(num)]
# initialize
for i in range(1,num+1):
for j in range(1,num+1):
if j%i == 0:
if door[j-1] == 1:
door[j-1] = 0
else :
door[j-1] = 1
count = 0
for i in range(0,num):
if door[i] == 1:
count += 1
print ("Open door : ", count)
criminal(120)
public class Prison {
public static void main(String[] args) {
int[] a = new int[121];
for(int i = 1 ; i <= 120;i++){
a[i]=1;
}
for(int i = 1 ; i <= 120;i++){
for(int j = 1 ; j <= 120/i ; j++){
a[i*j]*=-1;
}
}
int exit=0;
for(int i=1; i<=120;i++){
if(a[i]==-1){
exit++;
}
}
System.out.println(exit);
}
}
이상한가요~?
door = rep(0, 120)
for(i in 1:120) door[seq(i, 120, i)] = ifelse(door[seq(i, 120, i)], 0, 1)
sum(door)
> sum(door)
[1] 10
무식하게 열었다 닫아봤어요 재밌는 문제 감사합니다
python 2.7.12
n = 120
a = [0]*n
for i in range(1,n+1) :
for j in range(1,n+1):
a[j-1] = [ a[j-1] , a[j-1] ^ 1][j % i ==0]
print sum(a)
result
10
jail = [False]*120
for i in range(1,121):
for n in range(len(jail)):
if not (n+1)%i:
jail[n] = not jail[n]
print(jail.count(True))
출력:
10
머리로 생각해보기:
n번째가 닫혀있다 열릴 경우는 문이 홀수번 닫혔다 열려야 하는 것이다. 이때, 간수가 복도를 n의 약수번째 돌때 문이 열리거나 닫히므로 n의 약수 개수는 홀수여야 한다.
n의 약수 개수를 구하는 식은
n = a^x * b^y * c^z * ...일때
(x+1)*(y+1)*(z+1)*...개입니다.
홀수*홀수로만 홀수가 만들어지므로,
x+1,y+1,z+1,...이 홀수
즉, x,y,z,...이 짝수
따라서, n은 제곱수
따라서 이 문제는 1부터 120까지 중 제곱수를 찾으라는 말과 같다
1,4,9,16,25,36,49,64,81,100 -> 10개
문을 여닫는 동작을 -1을 곱함으로써 문 번호에 표시했습니다. 최후에 -1로 남아있는 문이 열린 문으로 홀수 번 동작이 이루어져야 하니 제곱수로 푸는 방법이 더 영리한 것 같네요
#prisoners
def door_move(door_number,n):
k=1
while n*k<len(door_number):
i=(k*n)-1
door_number[i] *= -1
k+=1
def main(prisoner_number):
door_number=list(range(1,prisoner_number+1))
x=1
while x <= len(door_number):
door_move(door_number,x)
x+=1
return [x for x in door_number if x<0]
if __name__ == '__main__':
main(120)
python으로 해봤습니다.
jail=[]
for i in range(0,119):
jail.append(1)
for n in range(1,121):
for j in range(1,121):
if j%n == 0:
if jail[j-1] == 0:
jail[j-1]=1
else :
jail[j-1]=0
jail.count(0)
#include <stdio.h>
int main(){
int door[121];
int s = 0;
for(int i = 1; i < 121; i++){ //처음에 문은 모두 닫혀 있다.
door[i] = 0;
}
for(int n = 1; n < 121; n++){ //간수는 복도를 120번 동안 지나간다.
for(int i = 1; i < 121; i++){
if((i % n) == 0){
door[i] = (door[i] == 0); //n번째 지나갈 때에는 n의 배수인 문들이 열려 있으면 닫고, 닫혀 있으면 연다.
}
}
}
for(int i = 1; i < 121; i++){
if(door[i]){
s++;
}
}
printf("%d", s);
}
#include <iostream>
using namespace std;
int main(void)
{
int arr[120];
int i=0;
int j=0;
int k=0;
int count = 0;
for(i=0;i<120;i++)
{
arr[i] = 0;
}
for(i=1;i<121;i++)
{
j = i;
while(j<121)
{
if(arr[j-1] == 0)
{
arr[j-1] = 1;
}
else
{
arr[j-1] = 0;
}
j += i;
}
}
for(k=0;k<120;k++)
{
if(arr[k] == 1)
{
count++;
}
}
cout<<count<<"\n";
return 0;
}
gates = [False for i in range(120)]
for i in range(1,120+1):
for j in range(1, 120+1):
if j%i == 0:
gates[j-1] = not gates[j-1]
print(gates.count(True))
package Prisoners120;
public class Prisoner {
static int[] prisoners = new int[120]; // 0 닫힘, 1 열림
public void init(){
for (int i = 0; i < prisoners.length; i++) {
prisoners[i] = 1;
}
}
public int calculateMultiple(int num){
int multipleNum = 1;
while(multipleNum<num){
for (int i = 2; i <= 120; i++) {
int tmp = multipleNum*i;
if(tmp<num){
if(prisoners[tmp-1]==1)
prisoners[tmp-1] = 0;
else
prisoners[tmp-1] = 1;
//System.out.print(tmp+" "); num의 배수 죄수들
}
}
//System.out.println();
multipleNum++;
}
return -1;
}
public int countJailbreakers(int[] prisoners){
int count = 0;
for (int i = 0; i < prisoners.length; i++) {
if(prisoners[i]==1)
count++;
}
return count;
}
public static void main(String[] args) {
Prisoner prisoner = new Prisoner();
prisoner.init();
prisoner.calculateMultiple(120);
System.out.println(prisoner.countJailbreakers(prisoners)+"명이 석방되었다.");
// for(int pri : prisoners){ // 마지막에 감방 문 열림 현황
// System.out.print(pri + " ");
// }
}
}
기계적 방법
l = list(1 for x in range(120))
for i in range((0+1), (119+1)+1):
for j in range(i, (120//i)*i+1, i):
l[j-1] *= -1
print(l.count(-1))
또는 제곱수 세기
print(sum(1 for x in range(1, 121) if (x**(1/2))%1==0))
파이썬 3.5.2 64
기계적 방법
l = list(1 for x in range(120))
for i in range((0+1), (119+1)+1):
for j in range(i, (120//i)*i+1, i):
l[j-1] *= -1
print(l.count(-1))
또는 제곱수 세기
print(sum(1 for x in range(1, 121) if (x**(1/2))%1==0))
파이썬 3.5.2 64
Java
import java.util.function.BiFunction;
public class Prisoner {
public int num;
public boolean state;
public Prisoner(int num) {
this.num = num;
this.state = false;
}
public static void main(String[] args) {
Prisoner[] pList = new Prisoner[120];
for (int i = 0; i < 120; i++) {
pList[i] = new Prisoner(i+1);
}
BiFunction<Integer, Integer, Boolean> warding = (num, check) -> num % check == 0;
for (int ward = 1; ward <= 120; ward++) {
for (int i = 0; i < 120; i++) {
if (warding.apply(pList[i].num, ward)) {
pList[i].state = !pList[i].state;
}
}
}
int releaseCount = 0;
for (int i = 0; i < 120; i++) {
if (pList[i].state) releaseCount++;
}
System.out.println(releaseCount);
}
}
결과 : 10
C로 작성하였습니다.
근데 문이 열려있으면..조건에서 if (room_open[i] == open) { prisoner++ } 라고 하니까, 카운팅이 안되더라구요.. 혹시 왜그런지 아시는 분 있으신가요? ㅠㅠ
#include <stdio.h>
typedef enum {
close,
open
}room_status;
int main() {
//TRUE = 열림, FALSE = 닫힘
//처음에 문은 모두 닫혀있다.
room_status room_open[120] = { close, };
static int aisle = 120;
int prisoner = 0;
int i, j = 1;
int multiple = 0;
//간수는 복도을 120번 지나간다.
for (i = 1; i <= aisle; i++) {
j = 1;
//N번째 지나갈 떄, N의 배수인 문들이 열려 있으면 닫고, 닫혀있으면 연다.
//N번째 : i
//배수 계산용 변수 : j
while (i*j <= 120) {
room_open[(i*j)-1] = ~room_open[(i*j)-1];
j++;
}
}
//문이 열려있으면 석방
for (i = 0; i < 120; i++) {
if (room_open[i] != close) {
prisoner++;
}
}
printf("석방되는 죄수는 %d 명 \r\n", prisoner);
system("pause");
return 0;
}
int offender()
{
int result = 0;
bool offenders[120] = { false, };
for (int i = 1; i <= 120; i++)
{
for (int j = i; j <= 120; j += i)
{
if (offenders[j-1])
offenders[j-1] = false;
else
offenders[j-1] = true;
}
}
for (int i = 0; i < 120; i++) if (offenders[i]) result++;
return result;
}
int main()
{
printf("몇명?:%d\n", offender());
return 0;
}
그냥 이중 for문 돌면서 약수면 boolean 값을 바꿔주었습니다.
/**
* Created by moonti on 2016. 10. 16..
*/
public class Prisoner120 {
static boolean[] A = new boolean[121];
public static void main(String[] args) {
for (int i = 1; i<= 120; i++) {
for (int j=1; j<=120; j++) {
if (j%i == 0) {
A[j] = !A[j];
}
}
}
int count = 0;
for (int k = 1; k<= 120 ; k++) {
if (A[k]) {
count++;
}
}
System.out.print(count);
}
}
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
int a[120]={0,};
int i,j;
int sum=0;
for(i=0;i<120;i++){
for(j=0;j<120;j++){
if((j+1)%(i+1)==0){
if(a[j]==0)a[j]=1;
else a[j]=0;
}
}
}
for(i=0;i<120;i++){
if(a[i]==1){
printf("%d\n",i+1);
sum++;
}
}
printf("%d",sum);
system("PAUSE");
return EXIT_SUCCESS;
}
import math
print(sum(map(lambda x:1 if math.sqrt(x) % 1 == 0 else 0,range(1, 121))))
Python 3.5.2에서 작성하였습니다.
room = [0 for x in range(0,121)]
for x in range(1,121):
for y in range(x,121):
if y % x == 0 and room[y] == 0:
room[y] = 1
elif y % x == 0 and room[y] == 1:
room[y] = 0
print('석방된 죄수 수 :',room.count(1))
# 첨부터 끝까지 뺑뺑이 버전
#### 2016.12.14 D-435 ####
print('석방된 죄수 수 :',len([True for z in [len([y for y in range(1,x+1) if x % y == 0]) for x in range(1,121)] if z % 2 == 1]))
# 1~120까지 각 숫자마다 약수의 개수를 구해서 약수의 수가 홀수개인것만 찾아서 개수를 출력.
#### 2016.12.14 D-435 ####
$rooms = array_fill('1','120','0');
foreach($rooms as $room => $v1){
foreach($rooms as $i2 => $v2) if($i2%$room==0) $rooms[$i2] = ($rooms[$i2]==0)?1:0;
}
echo array_sum($rooms);
먼저하신분 풀이를 보고 배워갑니다.
def prison_break(n):
prison=[0]*n
for i in range(n):
for j in range(n):
if (j+1)%(i+1)==0:
prison[j]=1-prison[j]
return sum(prison)
prison_break(120)
public class Prison_120 {
private boolean prison[];
public Prison_120(){
prison = new boolean[120]; //true 열려있다. false 닫혀있다.
}
public void run(){
for(int i = 0; i < 120; i++)
for(int j = 1; (i+1)*j <= 120; j++)
prison[(i+1)*j-1] = open_or_close(prison[(i+1)*j-1]);
for(int i = 0; i < 120; i++)
if(prison[i] == true)
System.out.print(i + " ");
}
private boolean open_or_close(boolean door){
if(door == true)
return false;
else
return true;
}
}
Python 3.6.0 입니다 답 10으로 나옵니다
num_of_prisoner=120
door=[-1]*num_of_prisoner
for walk_cnt in range(1,num_of_prisoner+1):
for room_number in range(0,num_of_prisoner):
if room_number % walk_cnt == 0:
door[room_number] *= -1
print(sum(list(filter(lambda x: x==1, door))))
public class Prisoner {
public static void main(String[] args) {
int p = 120;
int c = 0;
for (int i = 1; i <= p; i++) {
for (int j = 1; j <= p; j++) {
if (j * j == i) {
c++;
}
}
}
System.out.println(c);
}
}
약수의 갯수가 홀수인 방은 열림 홀수개의 약수를 가지려면 제곱이 되는 수 1 = {1}, 4 = {1,2,4} .... 100 = {1,10,100}
이론적으로는 방마다 열리고 닫히는 횟수는 방의 숫자의 약수 개수 만큼이므로 약수가 홀수개인 방번호만 최종적으로 열려있게 됩니다. 약수가 홀수개 이려면 제곱수 여야 하고, 120은 10의 제곱과 11의 제곱 사이의 수 이므로 120까지의 제곱수의 개수는 10개입니다.
총 10명의 죄수가 출소할수 있습니다.
다음 코드는 단순히 행동을 그대로 해서 인원을 출력한 코드입니다.
package codingdojang;
public class prisoner_120th {
public static void main(String args[]){
int arr[]=new int[121];
//숫자의 편의를 위해 배열은 1~120으로 사용 0번째 배열 사용 안함
arr[0]=120; //의미없는숫자...
for(int i=1;i<=120;i++)
arr[i]=0;
//모든 죄수의 방은 문이 닫혀있음
for(int i=1;i<=120;i++){
for(int j=1;(i*j)<=120;j++){
if(arr[i*j]==0)
arr[i*j]=1;
else
arr[i*j]=0;
}
}
int count=0;
for(int i=0;i<=120;i++){
if(arr[i]==1)
count++;
}
System.out.println(count);
}
}
#include<stdio.h>
#define MAX 120
int main(void)
{
int prison[MAX];
int i,j,n=0;
for(i=0;i<MAX;i++)
prison[i] = 0;
for(i=1;i<MAX+1;i++){
for(j=1;j<MAX+1;j++){
if( j%i == 0){
if(prison[j-1]==1)
prison[j-1]=0;
else
prison[j-1]=1;
}
}
}
for(i=0;i<MAX;i++){
if(prison[i] == 1)
n++;
}
printf("%d",n);
}
나이브하게 일일이 확인하는 코드를 짰는데 역시 수학을 잘해서 알고리즘을 이쁘게 짜야 코드도 이쁘게 되는군요
// 120번째 죄수 - C
#include <stdio.h>
#define OPEN 1
#define CLOSE 0
int main(void)
{
int i, j, counter = 0;
int gate[121]; // 끝 인덱스를 120으로 만들어서 편하게 한다.
for (i = 0; i < 121; i++)
gate[i] = CLOSE;
for (i = 1; i <= 120; i++)
for (j = 1; j <= 120; j++)
if (i * j <= 120)
if (gate[i*j] == OPEN)
gate[i*j] = CLOSE;
else
gate[i*j] = OPEN;
else
break;
for (i = 1; i <= 120; i++)
if (gate[i] == OPEN)
counter++;
printf("%d", counter);
// 답은 10
}
# 1 : close, -1 : open
a = [1 for i in range(120)]
for i in range(1,len(a)+1):
for j in range(1,len(a)+1):
if j%i == 0:
a[j-1] = a[j-1]*(-1)
print (a.count(-1))
var prisoner = 120;
var canfree = n => Number.isInteger(Math.sqrt(n)); // 제곱수 판별
var released = Array.from(Array(prisoner), (_, i) => i + 1).filter(canfree);
console.log(`released Number : ${released.join(" ")}`);
console.log(`released count : ${released.length}`);
만약 간수가 홀수 번 문을 열거나 닫으면 죄수는 석방이고, 짝수 번 열거나 닫으면 죄수는 석방이 아닙니다. 이럴 경우 약수가 홀수 개인 수를 가진 방의 죄수만 석방이 되는데, 약수가 홀수 개인 수는 제곱수 뿐입니다. 그래서 1^2, 2^2, 3^2, .... 10^2까지 모두 10명이 석방됩니다.
prisoners = [0] * 120
for i in range(1, 121) :
for k in range(1, 121) :
if k % i == 0 :
if prisoners[k-1] == 0 :
prisoners[k-1] = 1
elif prisoners[k-1] == 1 :
prisoners[k-1] = 0
print(prisoners.count(1))
open = [False] * 120
for n in range(1, 121):
for i in range(n-1, 120, n):
open[i] = not open[i]
print(sum(open)) # 10
namespace _20170910
{
class Program
{
static void Main(string[] args)
{
bool[] door = new bool[121];
for (int i = 0;i<121;i++)
{
door[i] = false;
}
for (int i = 1; i <= 120; i++) //N번째 복도를 지나감
{
for (int z = 1; z <= 120; z++) //N번째 죄수를 확인
{
if(z%i==0)
{
door[z] = !door[z];
}
}
}
int count = 0;
for (int i = 1; i <= 120; i++)
{
if (door[i])
{
count++;
}
}
Console.WriteLine(count);
}
}
}
jail = [False] * 120
for i in range(1, 121):
for j in range(i, 121, i):
jail[j-1] = not jail[j-1]
print(jail.count(True))
x = int(input("숫자를 입력하세요"))
d = []
r = 0
for s in range(1,x+1):
d.append("FALSE")
for f in range(1,x+1):
for a in range(1,x+1):
if a%f == 0:
if d[a-1] == "FALSE":
d[a-1] = "TRUE"
elif d[a-1] == "TRUE":
d[a-1] = "FALSE"
for s in range(0,x):
if d[s] == "TRUE":
r += 1
print(r)
public class level_2_prisoner_get_free {
public static void main(String[] args) {
int count = 0; // 문이 열려있는 감옥 수.
boolean[] prison = new boolean[120]; // 열리거나 닫힌 경우 두가지뿐이기에.
for(int i = 0; i < 120; i++) // 문을 다 닫아줌.
{
prison[i] = false;
}
for(int i = 1; i <= 120; i++) // i 번째 지나갈 때.
{
for(int j = 1; j <= 120; j++) // j 번째 문.
{
if(j % i == 0 && prison[j-1] == true)
{
prison[j-1] = false;
}
else if(j % i == 0 && prison[j-1] == false)
{
prison[j-1] = true;
}
}
}
for(int i = 0; i < 120; i++)
{
if(prison[i] == true)
{
count++;
}
}
System.out.println(count);
}
}
답 : 10명.
파이썬 3.6
n,free = 120,0
doorlist = [0 for i in range(1,n+1)]
for N in range(1,n+1):
for i in range(1,n+1):
if i%N == 0:
if doorlist[i-1] == 0:
doorlist[i-1] = 1
else:
doorlist[i-1] = 0
if doorlist[N-1] == 1:
free += 1
print("석방된 죄수는 %d 명"%free)
*결과값
석방된 죄수는 10 명
prizon<-function(n){
num<-0
room<-c(1:n)
room[1:n]<-"FALSE"
for(i in 1:n){
for(j in 1:n){
if(i*j>n){break}
if(room[i*j]=="FALSE"){
room[i*j]<-"TRUE"
print(room)
}else{
room[i*j]<-"FALSE"
print(room)
}
}
}
for(k in 1:n){
if(room[k]=="TRUE"){
num<-num+1
}
}
print(room)
print(num)
}
prizon(120)
문을 실제로 열고 닫는 방법으로
free = 0
for m in range(1, 121):
door = -1
for n in range(1, 121):
if m % n == 0:
door *= -1
if door == 1:
print(m, "번 죄수 석방")
free += 1
print(free, "명 석방")
약수 개수 홀수 == 거듭제곱
free = 0
for m in range(1, 121):
if m**0.5 == int(m**0.5):
print(m, "번 죄수 석방")
free += 1
print(free, "명 석방")
a=[]
for n in range(1,121):
t=0
for m in range(1,n+1):
if n%m==0:
t=t+1
if t%2==1:
a.append(n)
print(a)
print(len(a))
``````{.python}
석방될 죄수의 수를 구하는 문제입니다.
120명의 죄수 방이 있는데 이 방들의 문을
교도관이 홀수회를 체크하면 열리고 짝수회를 체크하면 닫히도록 되어있습니다.(초기조건이 모두 닫힘이기 때문에)
1부터 6까지의 수만 테스트를 해 보았습니다. (괄호는 문을 체크한 수입니다.)
6의 경우 1번째, 2번째, 3번째, 6번째에 체크를 하여 모두 4회 체크하여 최종적으로 닫히게 됩니다.
1 : 1 (1)
2 : 1->2 (2)
3 : 1->3 (2)
4 : 1->2->4 (3)
5 : 1->5 (2)
6 : 1->2->3->6 (4)
...
해당 수의 약수를 체크하여 약수의 수가 2의 배수가 되는 경우에는 닫히기 떄문에 열리는 경우에 죄수가 석방됩니다.
(많은 사람들이 풀었듯이, 결국에는 약수의 수가 2의배수가 아닌 제곱수가 답으로 나옵니다.)
코드는 아래와 같습니다.
#include <stdio.h>
const int PRISONALNUM = 120;
int isDivisor(int n) { // 사실상 bool타입
int numOfDivisor = 0;
// 약수 체크
for (int i = 1; i <= n; i++) {
if (n % i == 0)
numOfDivisor++; // 해당 n의 약수의 갯수 증가
}
if (numOfDivisor % 2 == 1)
return 1;
return 0;
}
int main() {
int prisonal = 0;
for (int n = 1; n <= PRISONALNUM; n++) {
if (isDivisor(n))
prisonal++;
}
printf("석방자의 수 : %d\n", prisonal);
return 0;
}
#include <stdio.h>
int main()
{
int n, re=0;
printf("인원수를 입력하시오.");
scanf_s("%d", &n);
for (int i = 1; i <= n; i++) {
if (i*i <= n) re++;
}
printf("%d명이 석방됩니다.\n", re);
return 0;
}
public class cNt{
public static void main(String[] args){
int i, j, k;
int cnt = 0;
int [] a = new int [120];
for(i=0;i<120;i++){
for(j=0;j<120;j++){
if((j+1)%(i+1) == 0 && a[j] == 0)
a[j] = 1;
else if((j+1)%(i+1) == 0 && a[j] == 1)
a[j] = 0;
}
}
for(k=0;k<120;k++){
if(a[k] == 1)
cnt++;
}
System.out.println(cnt + "명");
}
}
Swift입니다.
import Foundation
var door = Array(repeating: false, count: 120)
for loopCount in 1...120 {
for i in 0..<120 {
door[i] = ((i + 1) % loopCount == 0) ? !door[i] : door[i]
}
}
print( door.reduce(0, {$0 + ($1 == true ? 1 : 0)}) )
l = [1] * 120
for i in range(1,121):
for n in range(1,121):
if n % i == 0:
l[n-1] = ~l[n-1]
print(l.count(-2))
public class hello {
public static void main(String[] args) {
int a = 120;
int b = 0;
for (int i = 1; i <= a; i++) {
for (int j = 1; j <= a; j++) {
if (j * j == i) {
b++;
}
}
}
System.out.println(b);
}
}
room = [0 for i in range(120)] # close = 0, open = 1
for k in range(1, 120):
for j in range(1, 120):
if(room[j] == 0 and j%k == 0): room[j] = 1
elif(room[j] == 1 and j%k == 0): room[j] = 0
print(room.count(1))
public class Prison {
public static void main(String[] args) {
String[] prison=new String[121];
prison[0]="#";
int count=0;
for(int i=1;i<prison.length;i++) {
prison[i]="c";
}
for(int i=1;i<=120;i++) {
int index=i;
for(int j=1;j<=120;j++) {
if(j%index==0) {
if(prison[j].equals("o")) {
prison[j]="c";
}else {
prison[j]="o";
}
}
}
}
for(int i=1;i<prison.length;i++) {
if(prison[i].equals("o")) {
count++;
}
}
System.out.println(count);
}
}
Python
import math
n = 120
door = [False]*(n+1)
for i in range(1, n+1):
for j in range(1, n+1):
if j % i == 0:
door[j] = not door[j]
print(door[1:].count(True))
#Another solution
print(math.floor(math.sqrt(n)))
public class Main {
public static void main(String[] args) {
Boolean[] door = new Boolean[121];
int count = 0;
for (int i = 1; i < 121; i++)
for (int j = 1; j < 121; j++) {
door[j] = door[j] == null ? false : door[j];
door[j] = j % i == 0 ? !door[j] : door[j];
}
for (int i = 1; i < 121; i++)
count += door[i] ? 1 : 0;
System.out.println(count);
}
}
tmp,old = 0,0
for i in range(1,121):
for j in range(i,121,i):
tmp += 2**j
old ^= tmp
tmp = 0
print(bin(old).count('1'))
a=[1]
a=a*120
for i in range(120):
for j in range(int(120/(i+1))):
a[(i+1)*(j+1)-1]=a[(i+1)*(j+1)-1]*(-1)
out=0
for k in range(120):
if a[k]==(-1):
out+=1
print(out)
# open = 1, close = 0 으로 보자.
prison = [0] * 120
# n은 간수가 복도를 지나가는 횟수, i 는 방 번호(1부터 시작)
n = 1
while n <= 120:
i = 1
while i <= 120:
if i % n == 0:
prison[i-1] = (prison[i-1] + 1) % 2
i = i + 1
n = n + 1
num_open = prison.count(1)
print(num_open)
저는 python 을 사용하였습니다. 1과 0사이의 전환을 위와 같이 표현해 보았습니다.
효율적인 탐색방법을 항상 고민해보아야 겠네요^^
%n명 죄수의 석방
n=120;
a(1:n)=0; %0:닫힘,1:열림
for i=1:n %간수가 지나다니는 횟수
for j=1:n %방 번호
if a(j)==0 && rem(j,i)==0
a(j)=1;
elseif a(j)==1 && rem(j,i)==0
a(j)=0;
end
end
end
for k=1:n
if a(k)==1
fprintf('%d\t',k);%석방번호
end
end
fprintf('\n')
fprintf('석방 인원: %d\n',sum(a));
public class KimSanghyeop
{
public static void main(String[] args)
{
boolean[] door = new boolean[120];
for(int f1=1;f1<=120;f1++)
{
for(int f2=1;f2<=120;f2++)
{
if(f2 %f1 ==0)
{
door[f2-1] =!door[f2-1];
}
}
}
int cnt=0;
for(int f1=0;f1<120;f1++)
{
if(door[f1])
{
cnt+=1;
}
}
System.out.println(cnt);
}
}
person = [False for x in range(120)]
for op in range(1, 121):
a = [x for x in range(121)][::op][1:]
for ch in a:
person[ch - 1] = not person[ch - 1]
final = [fil for fil in person if fil]
print(len(final))
person 리스트에 120명의 죄수를 수감시킨 뒤 방문이 열려있으면 True, 닫혀있으면 False로 표시합니다. 루프돌려 일일히 계산한 뒤 final리스트에 True값만 모아 final의 길이를 출력합니다. 답은 10나오네요
# 0: in prison
# 1: released from prison
status = [0 for x in range(0,120)]
for N in range(1,121): # prison guard
for j in range(1,121): # prisoners
if j % N == 0:
if status[j-1] == 0: status[j-1] = 1
else: status[j-1] = 0
print(N, status)
print(sum(status))
print([x+1 for x in range(0,120) if status[x] == 1])
출력: 10 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
답: 10명
def prisoner(n):
prison = list(0 for i in range(0, n))
for i in range(1, n+1):
count = 1
while True:
if i * count > n:
break
else:
prison[i * count - 1] += 1
count += 1
count = 0
for i in prison:
if i % 2 != 0:
count += 1
return count
print(prisoner(120))
doors="x"*120
for turn in range(1,121):
for door in range(1,121):
if door%turn==0:
if doors[door-1]=="o":
doors=doors[:door-1]+"x"+doors[door:]
else:
doors=doors[:door-1]+"o"+doors[door:]
print("%d prisoners will be released"%(doors.count("o")))
42번 Light More Light와 같은 문제입니다.
완전 제곱수를 찾는 방식의 해법을 사용하신 분들은 정말 대단하군요.
다만, 이 경우 방의 개수와 간수가 지나간 횟수가 다를 수 있다고 가정하면, 간수가 지나간 횟수 < 방의 수일 때는 완전 제곱수가 아닌 번째의 방문이 열려 있을 수 있습니다.
def main():
numdoors = visits = 120
doors = [False] * (numdoors + 1)
count = 0
for idx in range(1, numdoors + 1):
for visit in range(1, visits + 1):
if idx % visit == 0:
doors[idx] = not doors[idx]
if doors[idx]: count+=1
print(count)
if __name__ == "__main__":
main()
n=int(input());print(n-int(n**0.5))
바로 전에 풀었던 문제가 약수의 갯수가 홀수인 수(완전제곱수) 를 파악하는 문제여서 참고를 했더니 많은 도움이 되었읍니다.^^
L = [-1 for i in range(120)] for n in range(1, 120+1): for i in range(n-1, 120, n): L[i] *= -1 print(sum(x == 1 for x in L))
Python 의식의 흐름대로 풀어봤습니다.
prison = ['prison'] + [0] * 121
location = 1
for j in range(1, 121):
for i in range(1, 121):
if i % location == 0 and prison[i] == 0:
prison[i] += 1
elif i % location == 0 and prison[i] == 1:
prison[i] -= 1
location += 1
result = []
for idx, val in enumerate(prison):
if val == 1:
result.append(idx)
print("Release!! {0}th prison.".format(result))
print("Release number : {0}".format(len(result)))
import java.util.Scanner;
public class sol117 {
static int count = 120;
static boolean door[] = new boolean[count+1];
public static void solution() throws Exception {
// 간수 움직이는 턴
for(int i=1; i<=count; i++) {
// 간수가 움직일때 방문의 열고 닫음
for(int j=1; j<=count; j++) {
if(j%i == 0) door[j] = !door[j];
}
}
int check = 0;
for(int i=1; i<=count; i++) {
if(door[i]) check++;
}
System.out.println(check);
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
solution();
}
}
public class 백이십번째죄수 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("빈방");
for(int i=0; i<120; i++) {
list.add("닫힘");
}
for(int i=1; i<=120; i++) { //간수 횟수
for(int j=1; j<=(120/i); j++) {
if(list.get(i*j).equals("닫힘")) {
list.set(i*j, "열림");
}
else if(list.get(i*j).equals("열림")) {
list.set(i*j, "닫힘");
}
}
}
int count = 0;
for(int i=1; i<=120; i++) {
if(list.get(i).equals("열림")) {
count++;
}
}
System.out.println(count);
}
}
door = []
for a in range(120):
door.append(0)
def open_close(n):
c = 1
while n * c < 120:
if door[n * c - 1] == 0:
door[n * c - 1] = 1
elif door[n * c - 1] == 1:
door[n * c - 1] = 0
c += 1
for x in range(120):
open_close(x + 1)
free = 0
for b in door:
if b == 1:
free += 1
print(free)
open_list =[]
for i in range(1,121):
cnt = 0
for j in range(1,121):
if j <= i :
if i % j == 0:
cnt += 1
if cnt % 2 != 0:
open_list.append(i)
print(open_list)
python3 입니다.
n = 120
p = [False for i in range(1, n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if j % i == 0:
p[j-1] = not p[j-1]
print(p.count(True))
pri=[0]*120 #죄수 리스트 pri에 문이 닫힘을 의미하는 값 0을 120개 넣음
#만약 문이 열리면 값을 1로 바꿈
for i in range (0,120): #간수가 120번 지나감
for j in range (0,120): #간수가 지나갈때 각 죄수를 체크함
if (j+1)%(i+1)==0: #i및j가 0부터 시작하므로 각각 1을 더한값으로 배수를 판별
if pri[j]==0: #값이 1이면 0으로, 0이면 1로 바꾸어준다
pri[j]=1
else:
pri[j]=0
n=0 #문이 열려 석방될 죄수의 값을 저장한 변수
for i in range (0,120):
if pri[i]==1:
n+=1
print (n) # 결과 : 10
a = []
for i in range(120):
a.append(0)
for i in range(1, 121):
for j in range(1, int(120/i)+1):
if a[i*j-1] == 0:
a[i*j-1] = 1
else:
a[i*j-1] = 0
print(a.count(1))
prison = [0 for i in range(120)]
for i in range(1, 121):
for j in range(len(prison)):
if (j+1) % i == 0: prison[j]+=1
free_prison = list(filter(lambda x: x%2!=0, prison))
print(len(free_prison))
def jail(p):
door = [False]*p
for i in range(1, p+1):
door = [not door[d-1] if d % i == 0 else door[d-1] for d in range(1, len(door) + 1)]
return door.count(True)
if __name__ == '__main__':
prisoner = 120
print(jail(prisoner))
import math
a = list('0'.zfill(120))
release = 0
for i in range(1,len(a)+1):
for k in range(1,len(a)+1):
if k == 1:
a[k-1] = '1'
elif k%i ==0:
a[k-1] = int(a[k-1])+1
else:
continue
for i in range(0,len(a)):
if int(a[i])%2 == 1:
release += 1
else:
continue
print(release)
파이썬3입니다.
freePrisoner = [x for x in range(1,121) if (x**.5).is_integer()]
print(f'Free prisoner is {freePrisoner}.\nAnd the number of free prisoner is {len(freePrisoner)}')
d=dict()
for i in range(1,121):
d[i]=d.get(i,"closed")
w=1
while w<=120:
for i in range(1,121):
if i%w==0:
if d[i]=="closed":
d[i]="opened"
elif d[i]=="opened":
d[i]="closed"
w+=1
c=0
for keys in d.keys():
if d[keys]=="opened":
c+=1
print(c) #10
room = list(range(1,121))
room[0]=0
for i in range (1, 121) :
for j in range (1,121) :
if j%i ==0 :
if room[j-1]>1 :
room[j-1] = 1
elif room[j-1] == 1 :
room[j-1]=0
else :
room[j-1]=1
print(room.count(1))
#include<stdio.h>
int main()
{
int i,j;
int ary[120]={0,};
for(i=0;i<=119;i++)
{
for(j=0;j<=119;j++)
{
if((j+1)%(i+1)==0)
{
if(ary[j]==0) ary[j]=1;
else if(ary[j]==1) ary[j]=0;
}
}
}
j=0;
for(i=0;i<=119;i++)
{
if(ary[i]==1)
j++;
}
printf("%d",j);
return 0;
}
door = [False for i in range(0, 120)]
for k in range(1, 121):
for i in range(1, 121):
if i % k == 0:
door[i - 1] = not (door[i - 1])
print(door.count(True))
import math as m
def finds(number):
counts=0
for i in range(1,121,1):
if int(m.sqrt(i))==m.sqrt(i):
counts+=1
return counts
print(finds(120))
let arr = new Array(120).fill('닫힘');
for (let i = 1; i <= 120; i++) {
for (let j = 0; j < 120; j++) {
if((j+1)%i==0)
change(j);
}
}
let result=arr.filter(el=>el=='열림')
console.log(result.length);
function change(j){
(arr[j]=='열림')?arr[j]='닫힘':arr[j]='열림'
}
prison={}
for i in range(1,121):
prison[i]=0
for i in range(1,121):
for n in range(1,121):
if 120>=i*n:
prison[i*n]+=1
elif 120<i*n:
break
total = 0
for i in range(1,121):
if prison[i]%2==1:
total+=1
print(total)
def door_initiate(n):
gate_list = []
for i in range(int(n)):
gate_list.append('0')
return gate_list
def door_check(_input):
print('{} gates are closed'.format(_input.count('0')))
print('{} gates are open'.format(_input.count('1')))
def multiple(a, n):
result = []
for i in range(a, n+1):
if i % a == 0:
result.append(i)
# print(result)
return result
# print(multiple(2, 120))
def func(n):
door_list = door_initiate(n)
door_check(door_list)
for i in range(1,int(n)+1):
print('ROUND {}'.format(i))
for number in multiple(i,n):
# print('NUMBER {}'.format(number))
if door_list[number-1] == '0':
door_list[number-1] = '1'
else: door_list[number-1] = '0'
# print(door_list)
door_check(door_list)
# print(door_list)
free_num_list = []
for i in range(len(door_list)):
if door_list[i] == '1':
free_num_list.append(i+1)
print(free_num_list)
func(120)
120개가 싫으시다구요 ? 한 300000개는 해보고 싶은데 부담되신다구요 ? 이걸 쓰시면 됩니다 !
print(int(int(input("명 : "))**0.5))
그냥 제곲근을 정수로 바꾼거 아니냐고요? 그게 정답니다 !
#codingdojing_120th_prisoner
'''
각 문을 지나는 수가 홀수면 죄수는 석방된다.
n번째 문을 지나는 횟수는 n의 약수의 개수와 같다.
n의 약수의 개수가 홀수이려면, 제곱근의 형태여야 한다.
ex) x^a x y^b -> 약수의 개수는 (a+1)x(b+1)
'''
#120번째 이하의 제곱근의 개수는
print(len(range(1,int(120**0.5) + 1))) #10명
count = 0
for i in range(1,121):
nlist = [x for x in range(1,i+1) if i % x == 0]
if len(nlist)% 2 != 0:
count += 1
print(count)
def prisoner(a):
for i in range(1,len(a)): # 지나가는 횟수
for n in range(1,len(a)): # 방 번호
if n%i == 0: # 방번호가 지나가는 횟수의 배수라면
a[n] = a[n]*(-1)
else:
continue
return a.count(-1)
if __name__ == '__main__':
a = [1]*121
print(prisoner(a))
# 각 문의 배수가 반복된 수를 배열화
arr=[]
for k in range(1,121):
n=1
while k*n <= 120:
arr.append(n*k)
n+=1
# 배수가 홀수번 반복된 문은 석방
num = 0
for i in range(1,121):
if arr.count(i)%2 ==1:
num +=1
print(num)
// Rust // 수학적 방법 보다는 그냥 시뮬레이션으로...
fn prisoners(n: usize) -> usize {
let mut vec = vec![false; n];
for i in 1..n+1 { //i번째 지나감(1~n)
let mut j = 1; //i의 배수
while i * j <= n {
vec[i * j - 1] = !vec[i * j - 1];
j += 1;
}
}
vec.iter().map(|&d| d as usize).sum()
}
fn test() {
assert_eq!(prisoners(120), 10);
}
n=120
gate = [-1 for x in range(n+1)]
for walk_num in range(1,n+1):
for gate_num in range(1,n+1):
if gate_num % walk_num == 0:
gate[gate_num] *= -1
print(gate.count(1))