[백준알고리즘] 9095번: 1, 2, 3 더하기 -Python

[백준알고리즘] 9095번: 1, 2, 3 더하기 -Python

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

9095번: 1, 2, 3 더하기

동적 계획법으로 문제를 해결했다. 한 번 DP문제를 풀기 시작하니 역시 처음에만 어렵고 술술 잘 풀린다..

 

우선 이 문제는 각 수가 주어지면 그 수를 1, 2, 3만을 더해서 만들 수 있는 경우의 수를 구하는 문제이다. 처음에 초기 값을 1, 2, 3을 만들 수 있는 개수인 1, 2, 4만 주었다. 그 이후 N을 만들 때까지 반복해서 구해주었다.

 

1, 2, 3만을 더해서 N으로 만들기 위해서는 세 가지 경우가 존재한다.

 

1. N-1에 1을 더하기 -> N-1을 만드는 경우의 수

2. N-2에 2를 더하기 -> N-2를 만드는 경우의 수

3. N-3에 3을 더하기 -> N-3을 만드는 경우의 수

 

따라서 N을 만들기 위한 경우의 수는 N-1, N-2, N-3을 만드는 경우의 수들의 합이다.

 

import sys

N = int(sys.stdin.readline())
dp = [0, 1, 2, 4]

for _ in range(N):
    T = int(sys.stdin.readline())
    for i in range(len(dp), T+1):
        dp.append(dp[i-1] + dp[i-2] + dp[i-3])
    sys.stdout.write(str(dp[T]) + "\n")

 

2020.03.08 

오늘 새로 풀어봤는데 DP인줄 모르니까 DP로 안풀었다... 풀때마다 푸는 방식이 바뀌니 참....

이번에는 set을 이용해서 구해주었다. 10까지 모두 구해준 후 set의 입력값에 따라 set의 길이를 출력해주었다.

 

import sys

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

table = {1:set('1')}
for i in range(2, 11):
    table[i] = set()
    before = table[i-1]
    for b in before:
        table[i].add(b + '1')
        table[i].add('1' + b)
        if b[-1] == '1':
            table[i].add(b[:-1] + '2')
        elif b[-1] == '2':
            table[i].add(b[:-1] + '3')
        if b[0] == '1':
            table[i].add('2' + b[1:])
        elif b[0] == '2':
            table[i].add('3' + b[1:])
            
for _ in range(testcase):
    n = int(sys.stdin.readline())
    print(len(table[n]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다