[알고리듬] #57 크리스마스 선물

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

남반구의 크리스마스

 

크리스마스 선물

크리스마스가 되면 즐겨 부르는 ‘열 이틀의 크리스마스(The Twelve Days of Christmas)'라는 노래가 있습니다.
그런데 요즈음에는 이 노래의 가사를 바꾸어 부르는 사람이 많습니다.

첫째 날에는, 선물 하나.
둘째 날에는, 다른 선물 하나에 두 개 더.
셋째 날에는, 또 다른 선물 하나에, 또 다른 두 개 더에 세 개 더.
넷째 날에는, 또 다른 선물 하나에, 또 다른 두 개 더에, 또 다른 세 개 더에. 네 개 더.
:
:

 

이렇게 열둘째 날까지 계속 합니다. 욕심도 많습니다.
열둘째 날까지 선물을 다 챙기면 모두 몇 개가 될까요?
받을 선물의 개수를 구하여 보세요.

 

1. 문제의 원형

그리스의 피타고라스 학파 사람들은 모든 숫자는 점(monad, 모나드)으로 구성된 아름다운 모양을 가지고 있으며,
그 모양은 우주에 있는 어떤 것을 나타낸다고 생각했습니다.
그래서 점들의 아름다운 구성에 관심이 많았는데 특히 위의 그림과 같이 점을 정삼각형 모양으로 배치했을 때의 숫자인 1, 3, 6, 10, 15 등을 '삼각수(triangular number)'로 이름 붙이고 흥미로워 했습니다.
삼각수는 다음과 같이 표현할 수도 있습니다.

 

• 1, (1+2), (1+2+3), (1+2+3+4), (1+2+3+4+5), .....
  1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, .....

2.  문제 분석

날짜와 그날 받을 선물의 숫자를 표로 만들어 보았습니다.

첫째 날은 1부터 1까지의 합,

둘째 날은 1부터 2까지의 합,

셋째 날은 1부터 3까지의 합,

이렇게 열둘째 날까지 반복하고, 각 날짜의 합을 모두 더하면 열이틀 동안 받은 선물의 개수가 됩니다.

 

3. 코딩

단계적으로 코딩을 완성하여 봅시다.

 

3-1 기본 형태

다음과 같이 출력되도록 코딩하여 보세요.

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 
1 2 3 4 5 6 7 
1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 11 
1 2 3 4 5 6 7 8 9 10 11 12 

 

n=12
for i in range(1,n+1):
    for j in range(1,i+1):    # 1부터 i까지 
        print(j,end=' ')
    print()                   # 줄 바꿈

 

3-2 날짜별 합계 구하기

다음과 같이 출력되게 하여 보세요.

1  sum= 1
1 2  sum= 3
1 2 3  sum= 6
1 2 3 4  sum= 10
1 2 3 4 5  sum= 15
1 2 3 4 5 6  sum= 21
1 2 3 4 5 6 7  sum= 28
1 2 3 4 5 6 7 8  sum= 36
1 2 3 4 5 6 7 8 9  sum= 45
1 2 3 4 5 6 7 8 9 10  sum= 55
1 2 3 4 5 6 7 8 9 10 11  sum= 66
1 2 3 4 5 6 7 8 9 10 11 12  sum= 78

n=12
for i in range(1,n+1):
    t=0                      # 날짜가 바뀌면 다시 0
    for j in range(1,i+1):
        t+=j                 # 그날의 선물 개수 합 
        print(j,end=' ')
    print(' sum=',t)

3-3 선물의 개수 누적

그날까지 받은 선물을 모두 더하여 다음과 같이 출력되게 하여 보세요.

1  sum= 1    tot= 1
1 2  sum= 3    tot= 4
1 2 3  sum= 6    tot= 10
1 2 3 4  sum= 10    tot= 20
1 2 3 4 5  sum= 15    tot= 35
1 2 3 4 5 6  sum= 21    tot= 56
1 2 3 4 5 6 7  sum= 28    tot= 84
1 2 3 4 5 6 7 8  sum= 36    tot= 120
1 2 3 4 5 6 7 8 9  sum= 45    tot= 165
1 2 3 4 5 6 7 8 9 10  sum= 55    tot= 220
1 2 3 4 5 6 7 8 9 10 11  sum= 66    tot= 286
1 2 3 4 5 6 7 8 9 10 11 12  sum= 78    tot= 364

n=12
s=0
for i in range(1,n+1):
    t=0
    for j in range(1,i+1):
        t+=j
        print(j,end=' ')
    s+=t    
    print(' sum=',t,'   tot=',s)​

 

3-4 코딩 완성

문제의 답인 364만 출력하여 보세요.

n=12
s=0
for i in range(1,n+1):
    t=0
    for j in range(1,i+1):
        t+=j
    s+=t    
print(s)

'''
s와 t를 초기화하는 곳,
들여쓰기 등을 충분히 이해하세요.
'''​

3-5 더욱 간단히

더욱 간단하게 코딩할 수도 있습니다.

원리를 분서하세요.

n=12
s,t=0,0
for i in range(1,n+1):
    t+=i
    s+=t
print(s)

 

 

3-6 더 더욱 간단히

n=12
s=0
for i in range(1,n+1):
    s+=i*(i+1)//2
print(s) 

'''
1부터 i까지의 자연수 합은 i*(i+1)//2입니다.
'''

 

 

수고하셨습니다.

오늘 끝.