[알고리듬] #19 산타클로스

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

 

도전할 준비가 되었습니까?

도전!

 

1. 산타클로스

산타클로스도 심심하면 작은 요정(elf)을 도와서 장난감을 만듭니다.

자동차를 50개 만들고, 기차를 50개 만들고 이렇게 번갈아 돌아가며 한 시간에 30개씩 만듭니다.

장난감 1개를 만드는 시간은 같으며 쉬지 않고 만듭니다.

오전 8:00에 시작하여 방금 108개의 자동차를 만들었습니다.

지금은 오후 몇 시 몇분일까요?

답은 오후 2시 56분입니다.

 

이러한 문제를 알고리듬에서는 다음과 같이 일반화 시켜서 출제합니다.

 

‘산타클로스도 심심하면 작은 요정(elf)을 도와서 장난감을 만듭니다.

자동차를 a개 만들고, 기차를 b개 만들고 이렇게 번갈아 돌아가며 한 시간에 n개씩 만듭니다.

장난감 1개를 만드는 시간은 같으며 쉬지 않고 만듭니다.

오전 h시 m분에 시작하여 방금 car개의 자동차를 만들었습니다.

a, b, n, h, m, car를 알 때, 지금은 오후 몇 시 몇 분인가 구하여 보세요.

장난감 한 개를 만드는 시간은 정수 분입니다.

답은 밤 12 시를 넘지 않는 오후 시간이며, 시와 분의 숫자만 출력합니다.

 

이 문제에 도전할 사람만 아래를 보세요.

천하의 영재 여러분!

좋은 보석은 원석을 잘 다듬어야 얻을 수 있습니다.

다듬지 않은 원석은 돌멩이입니다.

 

인간은 자신이 자신을 다듬습니다.

도망가서 돌멩이가 되겠습니까? 도전하여 보석이 되겠습니까?

 

당신은 도전을 선택하였습니다.

장래가 촉망되는 젊은이 입니다.

기대하는 바 큽니다.

응원합니다!

1-1.문제 분석(problem anaysis)

문제의 핵심만 요약 ·정리하여 보세요.

• 자동차 a개, 기차 b개를 번갈아 돌아가며 만든다.
• 한시간에 n개를 만든다 (1개 만드는 시간은 모두 같으며 정수이다).
• 시작 시간은 오전 h시 m분이다.
• car개의 자동차를 만든 시간을 구한다.
• 출력은 오후 시간이며 숫자만 출력한다.

문제의 핵심이 머릿속에 정리되어 있어야 합니다.

1-2. 입출력 설계( I/O design)

● 입력 설계(input design)

이 문제를 해결하려면 반드시 알아야 되는 정보는 무엇입니까?

• 돌아가며 만드는 자동차 개수(a)와 기차의 개수(b)
• 한 시간에 만드는 장난감의 개수(n)
• 시작 시간의 시(h)와 분(m)
• 만든 자동차 개수(car) 

 

●출력 설계(output design)

우리가 알고자 하는 것은 무엇입니까?

car개의 자동차를 만든 오후 시간

1-3. 알고리듬 설계(algorithm design)

● 문제 해결의 실마리

이 문제의 해결에 가장 중요한 것은 무엇입니까?

무엇을 알면 이 문제를 해결할 수 있을까요?

전체 장난감을 만드는데 걸린 시간

● 장난감 전체 개수

' 전체 장난감을 만드는데 걸린 시간'을 알려면 전체 장난감의 개수를 알면 됩니다.

' 전체 장난감의 개수'에 한개 만드는데 걸린 시간을 곱하면 됩니다.

어떻게 하면 ' 전체 장난감의 개수'를 알 수 있을까요?

- (자동차 a개, 기차 b개)  만드는 것을 한 회전이라 합시다

 

- car개의 자동차를 만들려면 최소 몇 회전 해야 하는지 구합니다.

(자동차 a개, 기차 b개) - (자동차 a개, 기차 b개) - (자동차 a개, 기차 b개) - .... 에서

한 회전에 a개의 자동차를 만들므로 회전 수는 ' car를 a로 나눈 몫' 즉, car // a 입니다.

 

- 장난감 전체 개수

전체 장난감은 한 회전에 (a+b)개 만들고, 마지막에  ' car를 a로 나눈 나머지' 만큼 자동차를 더 만들었습니다.

그러므로 전체 장난감 개수를 toy라 하면,

     toy=car / /a * (a+b) + car %a

● 전체 장난감을 만드는데 걸린 시간

장난감은 1시간에 n개를 만들므로 장난감 1개를 만드는데 걸린 시간은 분으로 계산하면 60 // n 입니다.

전체 장난감을 만드는데 걸린 시간은 toy * (60//n)  입니다(단위는 분).

 

● 오후 시간의 계산

오후 시간의 계산은 다음과 같은 방법이 간단합니다.

0시 0분 부터 종료시간까지의 분을 p라 하면

    p = q + r

즉,  0시 0분 부터 종료 시간까지의 분은 시작 (시간까지의 분) + (장난감을 만드는데 걸린 분) 입니다.

이 때 p를 60으로 나누면 몫은 시간이고, 나머지는 분이 됩니다.

오후 시간으로 출력해야하므로 시간은 12를 뺍니다.

 

1-3. 코딩하기

● 입력을 코딩하여 보세요.

a,b,n,h,m,car=50,50,30,8,0,108

● 산타가 만든 전체 장난감의 개수를 구하여 toy에 바인딩하세요.

a,b,n,h,m,car=50,50,30,8,0,108
toy=car//a*(a+b)+car%a

● 0시 0분부터 산타가 마지막 장난감을 만든 시간까지를 분으로 계산하여 time에  바인딩하세요.

a,b,n,h,m,car=50,50,30,8,0,108
toy=car//a*(a+b)+car%a
time=60*h+m+toy*(60//n)

● 종료 시각을 시는 ph에 분은 pm에 바인딩하여 출력하세요.

a,b,n,h,m,car=50,50,30,8,0,108
toy=car//a*(a+b)+car%a
time=60*h+m+toy*(60//n)
ph,pm=time//60-12,time%60
print(ph,pm)

 

이 문제를 해결한 당신을 크게 응원합니다 !

 

수고하셨습니다.

오늘 끝.