[BOJ] 1309

문제

me

• DP 알아냈다!!
• 하지만 추가되는 조건에 대한 생각을 하지 않았다
• 단순하게 그 전 것에서 더해야할 부분을 찾았고, 점화식을 dp[n] =dp[n-1]+dp[n-2]*2+1로 세웠다.
• 풀어보면 비슷한 논리이지만 선택할 수 있는 조건을 생각했다면 좋았을 것 같다.

solution

• 다음에 선택할 수 있는 조건은

  1. 아무것도 선택하지 않을 경우
     그 이전 것을 모두 사용할 수 있음
     dp[n-1][0]+dp[n-1][1]+dp[n-1][2]
  2. 왼쪽만 선택할 경우
     그 이전 것에서 왼쪽을 선택한 것 이외 사용할 수 있음
     dp[n-1][0]+dp[n-1][2]
  3. 오른쪽만 선택할 경우
     그 이전 것에서 오른쪽을 선택한 것 이외 사용할 수 있음
     dp[n-1][0]+dp[n-1][1]

• 코드

     import sys
     input = sys.stdin.readline
  
     n = int(input())
  
     dp=[ [0]*3 for _ in range(n)]
     dp[0][0]=1 # 아무것도 선택하지 않음
     dp[0][1]=1 # 왼 쪽
     dp[0][2]=1 # 오른 쪽
     for i in range(1,n):
        dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
        dp[i][1]=dp[i-1][0]+dp[i-1][2]
        dp[i][2]=dp[i-1][0]+dp[i-1][1]
  
     print(dp[n-1][0]+dp[n-1][1]+dp[n-1][2])