[알고리듬] #61 100마리의 닭

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

수탉(아빠닭)의 울음소리는 "꼬끼오~",

암탉(엄마닭)의 울음소리는 "꼬꼬댁 꼬꼬",

병아리는 "삐약삐약"

새벽을 알려주는 희망의 상징!

 

 

100마리의 닭

550년 경(6세기 초)에 중국의 장구건이 지은 <장구건산경(張邱建算經)>에는
'100마리의 닭(百雞, 빠이찌)’이라는 문제가 있습니다.

「今有雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。凡百錢買雞百只，問雞翁母雛各 幾何。」
‘수탉은 1마리에 5원, 암탉은 1마리에 3원, 병아리는 3마리에 1원이다.
100원으로 100 마리의 닭을 사려고 한다.
수탉, 암탉, 병아리를 각각 몇 마리씩 사면 되는가?’

 

 

1. 문제 분석

문제를 읽어보면 몇가지 확인해야 할 부분이 있습니다.

1. 100원을 모두 사용하여야 하는가? 
2. 수탉, 암탉, 병아리를 각각 1마리 이상 사야되는가?
3. 병아리는 3마리씩 묶음으로만 사야 되는가?

위의 3가지 의문에  대하여 문제에 명시적으로 표현하지 않았지만 출제 의도를 생각하면,

100원을 모두 사용하여, 꼭 100마리를 사야하며, 병아리는 3마리 묶음으로 사야하는 것 같습니다.

이러한 조건으로 문제를 해결합시다.

 

2. 알고리듬 설계

모든 경우를 발생시키고(status-space tree), 각 경우에 대하여 조건(100마리, 100원)에 맞는지 판단하면 되지 않을까요?

수탉 1마리, 암탉 1마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                         암탉 2마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                         :

                        암탉 99마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

수탉 2마리,   암탉 1마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                        암탉 2마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                         :

                        암탉 99마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

:

수탉 99마리, 암탉 1마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                        암탉 2마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

                         :

                        암탉 99마리, 병아리 3마리, 6마리, ..., 96마리, 99마리

 

3. 코딩하기

코딩에 도전하여 보세요.

n,m=100,100                                # 마리수와 돈 
for cock in range(1,n):                    # 수탉은 100마리 미만(암탉과 병아리가 있음)  
    for hen in range(1,n):                 # 암탉
        for chick in range(3,n,3):         # 병아리
            c1=cock+hen+chick==n           # 마리수 확인   
            c2=cock*5+hen*3+chick//3==m    # 돈 확인
            if c1 and c2:
                print(cock,hen,chick)
                
'''
3가지 방법이 있네요.
4 18 78
8 11 81
12 4 84

나의 컴퓨터로 처리시간은
약 0.1364초입니다.
'''

불필요한 계산을 줄여서 처리 시간을 단축할 수는 없을까요?

처리 시간을 줄일 수 있는 방법을 찾아서 프로그램을 수정하여 보세요.

n,m=100,100
for cock in range(1,n//5):               
    for hen in range(1,n//3):
        for chick in range(3,n,3):
            c1=cock+hen+chick==n
            c2=cock*5+hen*3+chick//3==m
            if c1 and c2:
                print(cock,hen,chick)
                
'''
2번 줄: 수탉은 20마리 이하입니다. 100원으로 한 마리 5원하는 수탉은 최대 20마리입니다.
3번 줄: 암탉은 100//3 마리 이하입니다.

나의 컴퓨터로 처리 시간은
약 0.009초입니다. 15배 빨라졌습니다.

시간을 더 줄일 수도 있습니다.
3번 줄:for hen in range(1,n//3-cock):
4번 줄:    for chick in range(3,n-cock-hen,3):

처리 시간은 약 0.004초, 또 처리 시간이 반으로 줄었습니다.
'''

4. 처리 시간 측정하기

파이썬의 time 내장 모듈은 주로 epoch time(에포크 타임)을 처리할 때 사용합니다. epoch time은 UTC(GMT+0) 기준으로 1970년 1월 1일 0시 0분 0초부터의 경과 시간을 나타냅니다. 인간이 사용하는 날짜와 시간은 시간대(time zone), 일광절약타임(date light saving), 윤년/윤달, 양력/음력 등 여러 가지 복잡한 개념들이 있습니다. 따라서 컴퓨터 시스템에서는 이렇게 복잡한 날짜와 시간을 모델링하는 대신에 epoch time을 이용해서 시간을 단순하게 숫자로 저장하고 처리하는 경우가 많습니다. epoch time을  timestamp(타임스탬프)라 부르기도 합니다.

 

다음 프로그램은 에포크 타임을 사용해서 처리 시간을 측정하는 예입니다.

import time                                 # 타임 모듈(time module)
start=time.time()                           # 시작 시간 체크
n,m=100,100
for cock in range(1,n//5):
    for hen in range(1,n//3-cock):
        for chick in range(3,n-cock-hen,3):
            c1=cock+hen+chick==n
            c2=cock*5+hen*3+chick//3==m
            if c1 and c2:
                print(cock,hen,chick)
end=time.time()                              # 종료 시간 체크
run=end-start                                # 실행 시간은 시작과 종료 시간의 차이  
print(run)

 

수고하셨습니다.

안녕!