[백준] 9095번 : 1, 2, 3 더하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

9095번: 1, 2, 3 더하기

 

1. 문제 설명

2. 풀이과정

해당 문제는 이전의 결과를 활용하여 해결하는 다이내믹 프로그래밍 문제이다.

여기서 이전 수의 1, 2, 3 조합의 경우에 모두 1을 추가하고 2와 3으로만 구성된 조합을 찾아 추가하면 다음 수의 1, 2, 3 조합의 경우가 도출된다.

해당 방법으로 1부터 입력받은 숫자까지 경우의 수를 구하고 입력받은 숫자의 각 경우의 순열 결과를 팩토리얼 함수로 구하면 해결할 수 있다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전체 테스트 케이스 횟수를 입력받는다. T = int(sys.stdin.readline())
3. 각 도출한 경우의 수의 순열 개수를 팩토리얼로 계산하기 위해 팩토리얼 함수를 생성한다. def Factorial(n)
4. 팩토리얼을 1부터 해당 수까지의 곱이므로 매개변수로 전달된 수가 1보다 크면 해당 수에 이전 수의 팩토리얼 값을 구하여 곱한 값을 반환한다. if (n > 1): return n * Factorial(n - 1)
5. 반면에 전달된 수가 1과 같거나 작으면 1을 반환한다. else: return 1
6. 입력받은 테스트 케이스의 횟수만큼 반복한다. for _ in range(T)
7. 1, 2, 3 조합의 수를 알고 싶은 값을 입력받는다. num = int(sys.stdin.readline())
8. 조합의 수를 저장할 변수를 생성하고 초기화한다. answer = 0
9. 경우의 수를 저장할 리스트를 2차원으로 생성하고 처음 1의 값의 경우를 저장한다. 각 조합의 경우를 리스트로 저장하고 이를 다시 리스트로 묶어 저장하기 위해 2차원 리스트로 생성한다. case = [[1]]
10. 2부터 입력받은 수까지 반복하며 각 경우의 수를 구한다. for i in range(2, num + 1)
11. 먼저 이전의 수의 각 경우의 수에 모두 1을 추가한다. for j in case: j.append(1)
12. 현재 수를 만들 때 최대로 더할 수 있는 2의 개수와 3의 개수를 구한다. count2 = i // 2  count3 = i // 3
13. 각 2와 3의 개수를 하나씩 늘려가며 2와 3만을 사용한 경우를 구한다. 3의 개수가 더 적을 수밖에 없으므로 3의 개수를 바깥 for 문으로, 2의 개수를 안쪽 for 문으로 하는 이중 for 문을 사용한다.이때 3의 개수가 0이 나오면 실행 자체가 안될 수도 있으므로 1을 더하여 한 번은 실행되도록 한다. for j in range(count3 + 1): for k in range(count2 + 1)
14. 만약 2와 3의 조합으로 이루어진 경우의 합이 현재 수와 동일하면 if (3 * j + 2 * k == i)
15. 2와 3으로만 이루어진 새로운 경우가 생겼으므로 새 경우를 저장할 리스트를 생성한다. li = []
16. 그리고 3의 개수만큼 반복하며 3을 추가하고 for _ in range(j): li.append(3)
17. 2의 개수만큼 반복하며 2를 추가한다. for _ in range(k): li.append(2)
18. 새로운 경우를 전체 경우에 추가한다. case.append(li)
19. 원하는 수의 모든 경우를 구한 뒤, 각 경우별로 순열의 경우를 구하여 더한다. for i in case
20. 전체 경우는 각 경우의 원소 전체 개수의 팩토리얼 값에 각 1, 2, 3 원소의 개수별 팩토리얼 값을 곱한 결과를 나눠주면 된다. answer += int(Factorial(len(i)) / (Factorial(i.count(1)) * Factorial(i.count(2)) * Factorial(i.count(3)))
21. 구한 총 경우의 수를 출력한다. print(answer)

반응형

3. 소스코드

import sys

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

def Factorial(n):
    if (n > 1):
        return n * Factorial(n - 1)
    else:
        return 1

for _ in range(T):
    num = int(sys.stdin.readline())

    answer = 0

    case = [[1]]
    for i in range(2, num + 1):
        for j in case:
            j.append(1)

        count2 = i // 2
        count3 = i // 3

        for j in range(count3 + 1):
            for k in range(count2 + 1):
                if (3 * j + 2 * k == i):
                    li = []
                    for _ in range(j):
                        li.append(3)
                    for _ in range(k):
                        li.append(2)

                    case.append(li)

    for i in case:
        answer += int(Factorial(len(i)) / (Factorial(i.count(1)) * Factorial(i.count(2)) * Factorial(i.count(3))))

    print(answer)