[알고리듬] #68 n개의 열린 문

[key word] 약수의 개수, 제곱수 판단

파이썬 실습창을 열 수 있습니다.실습창 열기

 

 

n개의 열린 문

n 개의 열린 문 앞을 n 명의 사람이 지나갑니다.

• 첫 번째 사람은 모든 열린 문을 닫으면서 지나갑니다.
• 두 번째 사람은 2번째, 4번째 등으로 2개마다 딛힌 문을 열면서 지나갑니다.
• 세 번째 사람은 3번째, 6번째 등으로 3개마다 열린 문은 닫고, 닫힌 문은 열면서 지나갑니다.
• 네 번째 사람은 4번째, 8번째 등으로 4개마다 열린 문은 닫고, 닫힌 문은 열면서 지나갑니다.
• 이러한 방법으로 모든 사람이 문 앞을 지나갔습니다.

그렇다면 n번째 문은 열려 있을까요 닫혀 있을까요?

열려 있으면 open, 닫혀 있으면 close를 출력하세요.

 

 

1. 문제 분석

문제를 단순화하여 분석해 봅시다.

다섯 사람이 다섯 개의 열린 문 앞을 지나갑니다.

첫째 사람은 모든 열린 문은 닫고 닫힌 문은 열었습니다.
둘째 사람은 두 칸 마다(2번째, 4번째, ...) 열린 문은 닫고 닫힌 문은 열었습니다.
셋째 사람은 세 칸 마다(3번째, 6번째, ...) 열린 문은 닫고 닫힌 문은 열었습니다.
:

 

이렇게 모두가 지나갔습니다.
지금  문들의 상태는 어떠할까요?

n=5                            # 5개의 문  
a=[0]*n                        # 0은 열림, 1은 닫힘. 모두 열려 있음
print(a)                       # 처음 상태 출력
for i in range(n):             # 지나가는 사람  
    for j in range(i,n,i+1):   # 문 번호. 증가값 i+1 유의
        a[j]=1-a[j]            # a[j]가 0이면 1, 1이면 0 
    print(a)                   # 한 사람이 지나간 상태 출력

'''
[0, 0, 0, 0, 0]  # 처음 상태
[1, 1, 1, 1, 1]  # 첫째 사람 자나간 후
[1, 0, 1, 0, 1]  # 둘째 사람 지나간 후
[1, 0, 0, 0, 1]
[1, 0, 0, 1, 1]
[1, 0, 0, 1, 0]  # 다섯째 사람 지나간 후

5번 문의 상태는 열려있습니다.
print(n-1)의 결과가 0이면 열려있고, 1이면 닫혀있는 것입니다.
'''

 

2. 코딩하기

위의 문제분석을 바탕으로 코딩하여 보았습니다.

msg=['open','close']
n=int(input())
a=[0]*n                        # 0은 열림, 1은 닫힘. 모두 열려 있음
for i in range(n):             # 지나가는 사람  
    for j in range(i,n,i+1):   # 문 번호. 증가값 i+1 유의
        a[j]=1-a[j]            # a[j]가 0이면 1, 1이면 0 
        
print(msg[a[n-1]])             # a[n-1]이 0이면 open, 1이면 close

 

문의 개수가 적으면 바르게 실행됩니다.

그러나 문의 개수가 많으면 실행시간이 너무 오래 걸립니다.

문의 개수가 많아도 빨리 실행되는 방법은 없을까요?

 

 

3  방법 개선

좋은 방법이 생각났습니다.

n번 문을 열거나 닫은 사람의 수가 짝수이면 열려있고, 홀수이면 닫혀있습니다.

n번째 문을 열거나 닫은 사람의 수는 n의 약수의 개수와 같습니다.

그러므로 n의 약수 개수를 구하면 n번 문의 열림과 닫힘을 판단할 수 있습니다.
예를 들어, 10번째 문이면 약수가 1,2,5,10으로 4개이므로 4사람이 지나가게 되고 짝수이므로 열려있게 됩니다.

 

위의 방법으로 코딩하였습니다.

msg=['open','close']
n=int(input())
s=1                        # 약수의 게수. 자신도 약수이므로 1개
for i in range(1,n//2+1):  # 1부터 자신의 반까지 나누어 봄
    if n%i==0:s+=1         # 약수의 개수 구함 
    
print(msg[s%2])            # s가 짝수이면 open, 홀수이면 close

'''
약수의 개수를 구할 때,
1과 자기 자신이 약수이므로  
n=10                        # 어떤 수 
s=2                         # 1과 자기자신으로 약수 2개                
for i in range(2,n//2+1):   # 2부터 조사
    if n%i==0:s+=1        
     
print(s)

이렇게 코딩하여도 되지않을까요?
n=1인 경우가 아니라면 가능합니다.
위와 같이하면 n=1일 때 결과가 2가 되어 틀리게 됩니다.
'''

 

4. 더 좋은 방법

• 제곱수(어떤 수를 제곱한 수)는 약수의 개수가 홀수이고, 그 외의 모든 수는 짝수개의 약수가 있습니다. 그러므로 문의 번호가 제곱수인가를 판단하여 제곱수이면 닫혀있고, 아니면 열려있습니다.
• 제곱수의 판단은 (제곱근을 제곱한 수)와 (원래의 수)가 같으면 제곱수입니다.
  다른 판단 방법은 제곱근이 정수이면 제곱수입니다.

위의 방법으로 코딩하였습니다.

msg=['open','close']
n=int(input())
r=(n==(n**0.5)**2)
print(msg[r])

'''
n**0.5가 n의 제곱근(루트 n)입니다.

3번 줄을 r=(n**0.5==int(n**0.5))와 같이 하여도 됩니다.

15129번째 문은 열렸을까요 닫혔을까요?
15129는 123의 제곱수입니다. (15129=123*123)
그러므로 close입니다.

'''

 

인류 지혜에 목말라 있어야 합니다.

배우고 배워도 배우고 싶어야 합니다.

무협의 절정고수가 되기 위하여 도를 닦는다고 생각하세요.

(도를 닦다: 터득하기 위하여 힘쓰다)

 

안녕!