[알고리즘] 백준 11726번 문제(DP)

date

Aug 16, 2023

slug

baekjoon-11726

author

status

Public

category

💻 Algorithm


n = int(input())
dp = [0]*(n+1)

if(n>2):
    dp[1]=1
    dp[2]=2 
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    print(dp[i]%10007)
else:
    print(n)

다이나믹 프로그래밍의 정석 문제인 느낌1!!

이 문제로 DP 감을 잡은 것 같다.

알게된 것 먼저 첫번째는 dp는 초기 0으로 선언을 해줘야 한다는 것.

여기에 메모제이션을 한다.

그리고 발화식을 세워보고 규칙을 발견하면

그대로 구현해보면 될 듯 하다.

명심할 것은 DP는 한번 계산한 문제는 절대 다시 계산하지 않는다는 것!!!

변수에 계산 값을 저장해두고 이용만 하자~

🤩

저같은 경우는 일단 dp를 선언하고 옆에다가 주석으로 dp[i][g]가 뭔지 선언하고 풉니다.

예를 들어 이 문제를 푼다고 했다면

변수를 선언 할때 밑에와 같이 dp[i]가 무엇인지 정의 해줍니다.

int dp[1001] = {}; //dp[i]는 크기가 i인 직사각형을 채우는 방법의 수

라고 지정한 다음

선생님 처럼 살짝 노가다를 하여 규칙성을 파학합니다.

크기가 i인 직사각형을 채우는 방법은

크기가 i-1인 직사각형을 채우는 방법의 +1이다,(세로로 긴 사각형1개만 가능함)

크기가 i-2인 직사각혀을 채우는 방법의 *2이다.(가로로 긴 사각형 2개와, 정사각형 1개가 가능함)

그리고 마지막으로 dp[1],dp[2]만 수작업으로 채워준 뒤

점화식 dp[i]=dp[i-1]+ 2*dp[i-2];을 이용하여 값을 구합니다.