새싹프로그래머의 이야기

https://www.acmicpc.net/problem/9095

문제: 주어진 숫자 n을 1,2,3의 숫자 합으로 나타내는 방법의 수 출력하기

풀이방법: 동적 계획법

풀이 설명: 

각 케이스 별로 봤을 때,

<n == 1> -> 1

(1)

<n==2> -> 2

(1,1) (2)

<n==3> -> 4

(1,1,1) (1,2) (2,1) (3)

<n==4> ->  7

(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (1,3) (3,1)

각 케이스별로 나오는 결과 값을 봤을 때, f(n) = f(n-3) + f(n-2) + f(n-1) (n >= 4) 가 성립하는 것을 찾을 수 있었습니다.

이에, 동적 프로그래밍을 통해 코드를 구현하였습니다.

풀이 코드:

import sys

n = int(sys.stdin.readline())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

dp = [1,2,4]

for i in range(3,max(array)):
    dp.append(sum(dp[i-3:i]))

for i in array:
    print(dp[i-1])

<초기 코드>

처음에는 문제에서 주어진대로 풀어보려고 했습니다.

문제 설명에서 나오는 숫자들이 순열과 일치한다고 생각하여 순열로 문제를 풀어보고자 하였습니다.

주어진 숫자로 만들 수 있는 1,2,3의 조합을 구하고, 이를 itertools의 permuations를 통해 나오는 결과 값의 갯수를 세면 정답을 구할 수 있을거라고 생각했습니다.(이때, permutation함수는 (1,1,2)의 각 1을 다른 개체로 보기 때문에 중간에 set 함수를 통해 결과 값에서 중복된 값을 제거해주었습니다.)

정답인 값들은 구할 수 있었지만 연산이 너무 많이 필요해서 시간초과가 발생하였습니다.

이에 , 다른 규칙을 찾고자 했고 위의 점화식으로 표현되는 규칙을 찾을 수 있어 '다이나믹 프로그래밍'으로 문제를 해결하였습니다

import sys

import itertools

n = int(sys.stdin.readline())

array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

for i in range(n):

    cnt = 0

    num = array[i]

    for a in range(num, -1, -1):

        for b in range((num - a) // 2, -1, -1):

            for c in range((num - a - 2 * b) // 3, -1, -1):

                numArray = []

                numArray.append(['1'] * a)

                numArray.append(['2'] * b)

                numArray.append(['3'] * c)

                numArray = list(itertools.chain.from_iterable(numArray))

                if (1 * a + 2 * b + 3 * c == num):
                    cnt += len(list(set(list(itertools.permutations(numArray, a + b + c)))))

    print(cnt)