[백준/9095/파이썬3(python3)] 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

입출력 예

입력	출력
3 4 7 10	7 44 274

풀이

test_case_count = int(input())
user_input_list = []

integer_list = [1, 2, 4]
for i in range(4, 11):
    integer_list.append(sum(integer_list[-3:]))

for i in range(test_case_count):
    user_input_list.append(int(input()))

for i in range(test_case_count):
    print(integer_list[user_input_list[i] - 1])

설명

동적 계획법(Dynamic Programming : 다이나믹 프로그래밍)이라는 분야를 처음 알게 되었던 문제이다. 여태 풀어왔던 문제들 중 가장 멘붕을 타기도 했고. 왜냐. 아예 내가 몰랐던 분야였는데 분류가 초등부로 돼있었기 때문이다. 그렇다. 나는 초등학생들도 쉽게 푸는 문제를 풀지 못해 끙끙댔던 것이다. 그렇게 나는 엄청난 상실감에 빠졌었다.

 근데 그게 오래가지는 않았다. 나는 전공자도 아니었던 데다가 당연히 모르는 분야가 있기 마련이라는 것을 점차 알게됐다. 분류가 초등학생으로 되어있든, 유치원생으로 되어있든 나는 아직도 경력 1년 미만의 초급개발자이고 아직 알고 있는 것보다는 알아야할 게 더 많다. 그런 입장이니 초등부 문제를 못 풀었다고 기죽어있을 필요는 없다는 걸 깨달았다. 그렇게 동적계획법이 무엇인지, 공부하고 스스로 문제를 풀게 됐다.

동적 계획법

동적 계획법(Dynamic Programming : 다이나믹 프로그래밍)이란 무엇인가? 사전적인 의미로는 이렇다.

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효울적으로 값을 구하는 알고리즘 설계 기법.

어떠한 계산 과정 중 앞에 나왔던 답을 재활용해 원하는 결과를 얻는 것이다. 그러니까 답을 구해 답을 구하고, 또 답을 구해서 답을 구하고 이 과정을 반복하여 결국 원하는 위치까지 가는 것, 그것이 바로 동적 계획법이다.

예시

이 문제를 예로 들어보자. 이 문제에서 일단 우리가 쓸 수 있는 정보는 다음과 같다.

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

이제 테이블로 살펴보자.

 

1을 만드는 방법
1을 이용	1

총 1개이다.

2를 만드는 방법
1을 이용	1 + 1
2를 이용	2

총 2개이다.

3을 만드는 방법
1을 이용	1 + 1 + 1
2를 이용	1 + 2
	2 + 1
3을 이용	3

총 4개이다.

이번엔 예제에서 나온 4를 만드는 방법을 나열해보자.

4를 만드는 방법
1을 이용	1 + 1 + 1 + 1
2를 이용	2 + 1 + 1
	1 + 2 + 1
	1 + 1 + 2
	2 + 2
3을 이용	3 + 1
	1 + 3

이렇게 총 7개라 할 수 있다. 아직 이 문제에 대한 패턴은 파악이 되지 않았다. 한번 5를 만드는 방법까지 손수 구해보자.

5를 만드는 방법
1을 이용	1 + 1 + 1 + 1 + 1
2를 이용	2 + 1 + 1 + 1
	1 + 2 + 1 + 1
	1 + 1 + 2 + 1
	1 + 1 + 1 + 2
	1 + 2 + 2
	2 + 1 + 2
	2 + 2 + 1
3을 이용	3 + 1 + 1
	1 + 3 + 1
	1 + 1 + 3
	2 + 3
	3 + 2

이렇게 총 13개이다. 이제 조금 어떤 패턴이 보인다. 1부터 해당 조건으로 만들 수 있는 수조합의 갯수를 살펴보자.

1은 1개, 2는 2개, 3은 3개, 4는 7개, 5는 13개이다. 이것을 배열로 만들어보면 이런 모양이다.

[1, 2, 4, 7, 13...]

 사실... 솔직히 말하자면 나는 이 문제에서 동적 계획법을 통해 답을 유추한다는 게 잘 납득이 안된다. 동적 계획법이라는 프로그래밍 기법을 몰랐을 때 이 문제를 처음 접했을 땐 그저 경우의 수와 패턴에만 집착했었다. 입력된 한 수가 있으면 1, 2, 3을 이용해 그 수를 만들 수 있는 모든 조합을 전부 구한 뒤에 해당 조합을 튜플로 구분하여(튜플은 순서가 다르면 다른 개체로 인식하므로) 가능한 모든 경우의 수를 수하는 방식으로 말이다. 근데 아무리 해도 너무 어려운 것이다. 이 문제를 접한 난이도대의 해결방법이 아니었다. 해서 결국 인터넷에 정답을 구글링해봤고 위와 비슷한 대답을 얻었긴 했는데... 뭔가 모호함이 있다고 해야하나.

 사실 이 문제에서 설파하는 동적 계획법이라는 게 잘 와닿지 않는다. 많은 인터넷의 답이 이런 식이었다.

1. 4의 케이스가 7이고, 5의 케이스가 13이다.
2. 4의 케이스인 7은 1, 2, 3의 케이스를 모두 더한 수이다.
3. 5의 케이스인 13은 2, 3, 4의 케이스를 모두 더한 수이다.
4. 그러니까 6의 케이스는 3, 4, 5의 케이스를 모두 더한 수일 것이다.

 하는 막연한 유추로 차후의 값을 구한다. 물론 수학은 굉장히 신비한 학문이라 이런식의 수열이 성립하는 경우가 많지만 대체 왜! 그런 확신을 할 수 있는지 그걸 모르겠다는 것이다. 이게 이 수일 때 이랬으니까 저 수일 때는 이럴 것이다 하는 그런 유추말이다...

 물론 수학을 잘 하는 사람에겐 이런 물음이나 질문이 굉장히 하찮게 느껴지기도 하겠지만 나에게는 이러한 호기심이 알고리즘 정립을 확신하거나 불신하게 되는 계기가 되곤 하므로 보다 확실한 무언가가 필요했다... 그게 바로 질문의 요다.

다이나믹 프로그래밍을 통해 얻은 결과값은 과연 신뢰할만 한가?

이것이 궁금하다.

각설하고, 위와 같은 일련의 수작업 및 과정들을 통해 점화식을 얻을 수 있다. 점화식이란 루프계산을 통해 원하고자 하는 답을 얻게 해주는 식을 말하는데 이 문제에서는 5를 넣었을 때 13을 뱉게 해주는 식을 말한다. 코드에서 볼 수 있겠지만 점화식은 다음과 같다.

sum(integer_list[-3:])

 파이썬 코드라서 조금 생소해보일 수도 있지만 해당 코드는 현재 인덱스에서부터 앞으로 3번째까지의 인덱스의 합을 구하는 코드이다. 해당 문제는 1, 2, 3을 이용하는 문제이기 때문에 만들어야 하는 수가 1, 2, 3인 경우를 제하고 4부터 시작하는데 4를 만들 수 있는 수의 합은 1, 2, 3을 만들 수 있는 경우의 수를 더하는 것이고 이것이 4에서부터 계속 이어지기 때문에 반복문은 4의 경우에서부터 시작한다.

 비록 동적 계산법이 이렇게 푸는 것이라 할지라도 뭔가 마음이 편치 않은 문제였다. 새로운 알고리즘 분야를 알게 됐고 스킬이 하나 늘어난 느낌이지만 뭔가 뒤가 개운치 못하다. 이렇게 장황하게 무엇인가를 쓴 적도 처음이고... 기억에 많이 남는 문제가 될 것 같다.