[DP] Sliver 3 9461 파도반 수열

문제

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

 

---

Dynamic Programming (DP) 알고리즘을 왜 사용하는가? 

재귀를 계속해서 사용하게 되면 비효율적이기 때문에 이미 계산한 값은 재활용할 수 있도록 하는 것!

 

 

설계 ✨

1. Dp로 풀 수 있는지 확인

Dp로 문제를 풀 수 있는지 확인하는 조건은 2가지가 존재한다. 

• 동일한 작은 문제들이 반복하여 나타나는지? (재귀를 사용할 수 있는지 파악하면 될 것 같아!)
• 부분 문제 최적 결과 값을 사용해 전체 문제의 최적의 결과를 낼 수 있는지? 

 

2. 문제의 변수 파악 

이 문제에서는 변수 n을 사용했다. 

1<= n<=100 → 이 변수가 얼마냐에 따라 결과값이 다르지만 그 결과를 재사용할 수 있도록 한다. 

 

3. 점화식 만들기

이제 점화식을 찾아보도록 하자.

1 1 1 2 2 3 4 5 7 9

f(1) = 1
f(2) = 1
f(3) = 1
f(4) = f(1) + f(2)
f(5) = f(2) + f(3)
f(6) = f(3) + f(4)

... 

이 관계들로 다음과 같은 점화식을 얻을 수 있다. 

f(n) = f(n-3) + f(n-2)

 

4. Memoization 

그 다음, 변수 값에 따른 결과를 저장할 배열을 미리 만들고, 그 결과를 나올 때마다 저장하고, 그 저장된 값 재사용하도록 구현해야한다. 

 

5. 기저 상태 파악하기

가장 작은 문제인 상태를 파악하는 것이다. 

이 문제에서는 이 부분이라고 파악된다.

f(1) = f(2) = f(3) = 1

 

해당 기저 문제에 대해 파악 후 미리 배열 등에 저장하거나 따로 조건을 걸어줘야한다!

 

6. 구현하기

이제 구현을 하면 되는데, 구현하는 방식에는 

Bottom-up과 Top-down 방식 2가지가 있다. 

편한 방식으로 사용하면 될 것 같다. 

 

Bottom-up

• Table에 저장된 값에 직접 접근
• for문 사용
• Tabulation

 

Top-down 

• 위에서부터 호출
• 재귀 활용
• 이미 이전에 계산을 완료한 경우 단순히 메모리에 저장되어있던 내역을 꺼내서 재활용

---

다음은 설계한 내용을 바탕으로 짠 코드이다.

# Top-down dp 

# 백준에서 주어진 n이 1부터 100까지이므로 
# 0번째는 사용하지 않기 때문에 101까지 공간을 만들어준다. 
dp = [0] * 101

def pado(n):
  # 기저 상태
  if n == 1 or n == 2 or n==3:
    return 1
  
  # 이미 계산한 적 있으면 그대로 반환
  if dp[n] !=  0:
    return dp[n]

  # 계산한 적 없으면 점화식에 따라 결과를 반환
  dp[n] = pado(n-3) + pado(n-2)
  return dp[n]

t = int(input())
for i in range(t):
  n = int(input())
  print(pado(n))

 

# Bottom-up dp 

# 기저상태 미리 dp에 저장
# 0번째는 사용X
# f(1) = 1, f(2) = 1, f(3) = 1
dp = [0] * 101
dp[1] = dp[2] = dp[3] = 1 

# dp = [0,1,1,1]로 해서 리스트에 추가하는 형식으로 하면 dp 테이블이 변형됨
def pado(n):
  
  # dp 테이블 index로 직접 접근
  for i in range(4,n+1):
    dp[i] = dp[i-3] + dp[i-2]
  
  return dp[n]

t = int(input())
for i in range(t):
  n = int(input())
  print(pado(n))