[백준/15989/파이썬] 1,2,3 더하기 4 - dp

---

소스코드

n = int(input())

def dyPro(n):

  if n <= 3 :

    return n

  dp = [0] * (n+2)

  dp[1] = 1

  dp[2] = 2

  dp[3] = 3

  for i in range (4,n+1):

    dp[i] = dp[i-3] + i //2 + 1

  return dp[n]

for _ in range (n):

  m = int(input())

  print(dyPro(m))

---

알고리즘

시간 제한이 1초라는 것은 1억번의 연산이라고 하며 N < 10,000 보다 작은 제한 조건이 있는 것으로 보아 DP느낌이 났다.

그래서 그냥 일일히 나열해봤다.

 

1 1
2 1+1
3 1+2
4 1+3
5 2+3
7 3+4
8 4+4
10 5+5
12 7+5
14 8+6

2
2
11

3
3
21
111

4
31

22
211
1111

5
3 2
3 11

221
2111
11111 

6
3 3
3 21
3 111

222
2211
21111
111111

7
3 31
3 22
3 211
3 1111

2221
22111
211111
1111111

8
3 32
3 311
3 221
3 2111
3 11111 

2222
22211
221111
2111111
11111111

9
22221
222111
2211111
21111111
111111111

 

뭐가 느껴질까?

1. 3으로 시작하는 숫자는 DP[I-3] 번째에 있는 애들과 숫자가 같다

2. 2로 시작하는 숫자는 2-> 1 1 이렇게 변하는 특성을 가지고 있고, 이는 i를 2로 나눈 값의 +1을 해준 값이다.