[알고리듬] #63 상하이 팔팔 가게

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

상하이 예원

 

상하이 팔팔 가게

상하이 8번가에 있는 88(팔팔) 가게에는
물건의 값이 8원 짜리 숟가락, 88원 짜리 접시, 888원짜리 그릇, 8888원짜리 밥통 등과 같이
8원, 88원, 888원, 8888원 짜리 물건들 만 있습니다.

이곳에서 10가지 물건을 10000 원에 샀습니다.
8원, 88원, 888원, 8888원 짜리를 각각 몇 개씩 샀을까요?

 

[참고]
중국 사람들은 8을 매우 좋아합니다.
8은 ‘빠’라고 읽는데 ‘돈을 번다’는 ‘빠차이(發財)’와 발음이 닮았기 때문입니다.
2002년 중국에서는 북경 올림픽을 8월 8일 8시 88분에 개막했습니다.
이것은 8월 8일 9시 26분을 의미합니다.
중국 사람들의 8에 대한 사랑을 엿볼 수 있습니다.

 

1. 바로 코딩하기

어떻게 프로그램을 짜야할 지 전체적인 구조가 머리 속에 떠 오르십니까?

바로 코딩하여 보세요.

n,m=10,10000                                  # 물건의 가지 수와 돈                                                         
for i in range(n+1):                          # 8원짜리, 0개부터 n개
    for j in range(n+1):                      # 88원짜리
        for k in range(n+1):                  # 888원짜리
            for l in range(n+1):              # l(엘)은 8888원짜리
                c1=i+j+k+l==n                 # 개수 체크 
                c2=i*8+j*88+k*888+l*8888==m   # 돈(금액) 체크
                if c1 and c2:
                    print(i,j,k,l)
                    
'''
답은 6, 2, 1, 1 입니다.
즉, 8원짜리 6개, 88원짜리 2개, 888원짜리 1개, 8888원짜리 1개입니다.
'''

 

2. 더 빠르게

위의 코드를 개선하여 더 빠르게 결과를 얻을 수는 없을까요?

 

• 생각하기

• 8원짜리를 몇개 샀습니다. 그러면 88원짜리는 최대 몇개 살 수 있을까요?
  전체 10개에서 8원짜리 개수를 뺀 개수입니다.
• 888원짜리는 최대 몇개?
  전체 10개에서 8원짜리와 88원짜리 개수를 뺀 개수입니다.
• 8888원자리는 8원, 88원, 888원 짜리 개수를 빼면됩니다.

위의 생각대로 코드를 수정하여 보세요.

n,m=10,10000
for i in range(n+1):
    for j in range(n+1-i):  # 이곳 수정               
        for k in range(n+1-i-j):  # 이곳 수정
            for l in range(n+1-i-j-k):  # 이곳 수정
                c1=i+j+k+l==n
                c2=i*8+j*88+k*888+l*8888==m
                if c1 and c2:
                    print(i,j,k,l)
                    
 '''
 간단한 아이디어가 실행 시간을 많이 단축시킵니다.
 '''

 

3.  더, 더 빠르게

답을 찾아서 출력하였으면 프로그램을 종료할 수는 없을까요?

때로는 답을 찾은 다음의 무의미한 실행을 중단시키고 싶을 때도 있습니다.

이러한 경우, 하나의 루프(loop, for 또는 while)를 벗어나게 하려면 break 문을 사용하면 됩니다.

그러나 다중 루프(2개 이상의 반복문)를 벗어나게 하려면 약간의 연구(?)가 필요합니다.

몇 가지 방법 중에서 비교적 간단힌 2가지 방법을 소개합니다.

 

3-1 고의적 에러 발생

n,m=10,10000
try:         # 에러가 없으면(정상적이면) 3번 줄에서 11번 줄까지 실행
    for i in range(n+1):
        for j in range(n+1-i):
            for k in range(n+1-i-j):
                for l in range(n+1-i-j-k):
                    c1=i+j+k+l==n
                    c2=i*8+j*88+k*888+l*8888==m
                    if c1 and c2:
                        print(i,j,k,l)    # 답을 찾았으면,
                        a=1/0             # 고의적 에러 발생(어떤 수를 0으로 나누면 에러)
except:pass   # 이곳은 에러가 발생되면 실행

'''
try ~ except(트라이 익셉트) 구문은 
에러가 없으면 try와 except 사이의 문장을 수행하고,
에러가 발생되면 except 다음을 수행합니다.
pass는 하는 일이 없습니다. 
문법적으로 except 다음에 실행할 문장을 적어야 하는데 할 일이 없는 경우 pass를 적습니다.
그러므로 에러를 만나면 종료하게 됩니다.

답을 찾았으면 에러를 발생시켜서 프로그램 전체를 종료시키는 구조입니다.
이 방법은 효과적이지만 편법(?)에 가깝습니다.
정상적이지는 않습니다.
'''

 

3-2  함수의 사용

아직 공부하지 않은 함수(function)을 사용하면 깔끔(?)하게 다중 반복문을 벗어날 수 있습니다.

다음 코드가 그 예입니다.

def shanghai():    # 여기부터 10번 줄까지가 함수입니다.
    for i in range(n+1):
        for j in range(n+1-i):
            for k in range(n+1-i-j):
                for l in range(n+1-i-j-k):
                    c1=i+j+k+l==n
                    c2=i*8+j*88+k*888+l*8888==m
                    if c1 and c2:
                        print(i,j,k,l)
                        return    # 모든 실행을 중단하고 호출한 곳(13번 줄)으로 복귀합니다.
                        
n,m=10,10000        # 실행시키면 이곳부터 실행합니다.
shanghai()          # 1번 줄의 shanghai() 함수를 호출(실행 시키는 것)합니다.

'''
다중 반복문의 탈출은 이 방법(함수 사용)을 추천합니다.
'''

 

점점 재미있는 방법들이 등장합니다.

새로운 세계는 우리를 즐겁게 합니다.

오늘도 수고하셨습니다.

안녕!