[백준15989/골5] 1, 2, 3 더하기 4 - Python

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

 

 

 

처음엔 점화식 풀어서 해야하는 줄 알고 엄청 고민했는데 결국 풀리지 않았다.

그래서 다른 블로그 도움 받았는데 이해하는데 꽤 오래 걸렸다.

for문 한 개 안에서 해결하려는 고정관념 때문에 생각도 못한 코드가 정답이었다.

 

 

다른 블로그에서는 dp 배열을 처음부터 1로 초기화 하고 시작했다. 문제 조건이 n은 양수이지만 그래도 dp[0] = 1 이 되는건 좀 찝찝했다.

1, 2, 3을 사용해서 0을 만들 수 있는 경우의 수는 0인데... 이해하는데 어려움이 있어서 최적화 없이 풀어봤다.

 

1. dp 테이블 0으로 초기화

2. 1만 사용해서 정수의 합 나타내는 경우의 수 : 모든 정수 다 한가지

3. 2추가 : 1로만 이루어진 정수에서 1+1 빼고 2 추가

4. 3추가 : 1 또는 2로만 이루어진 정수에서 1+1+1 또는 2+1 빼고 3 추가

 

성공 코드 1

# 1 : 1가지 (1)
# 2 : 2가지 (2, 1+1)
# 3 : 3가지 (3, 2+1, 1+1+1)
# 4 : 4가지 (3+1, 2+1+1, 1+1+1+1, 2+2)

dp = [0] * 10001

# 1로만 정수의 합을 나타내는 경우의 수 : 1가지
for i in range(1, 10001):
    dp[i] = 1

# 1 또는 2를 포함하여 정수의 합을 나타내는 경우의 수
dp[2] += 1  # 2 추가
for i in range(2, 10001):
    dp[i] += dp[i-2]

# 1 또는 2 또는 3을 포함하여 정수의 합을 나타내는 경우의 수
dp[3] += 1  # 3 추가
for i in range(3, 10001):
    dp[i] += dp[i-3]


for tc in range(int(input())):

    n = int(input())
    print(dp[n])

 

 

 

이렇게 풀고 나니까 원래 내가 봤던 블로그의 코드도 이해됐다.

성공 코드 2

# 1로만 정수의 합을 나타내는 경우의 수 : 1가지
dp = [1] * 10001

# 1 또는 2를 사용해서 정수의 합을 나타내는 경우의 수
for i in range(2, 10001):
    dp[i] += dp[i-2]

# 1 또는 2 또는 3을 사용해서 정수의 합을 나타내는 경우의 수
for i in range(3, 10001):
    dp[i] += dp[i-3]

for tc in range(int(input())):

    n = int(input())
    print(dp[n])

 

 

 

짱어렵다! 시리즈 더 풀어야지~