4869. [파이썬 S/W 문제해결 기본] 4일차 - 종이붙이기

#파이썬

##이문제는 아직 이해가 안돼서 질문 안받음

 

문제를 보자마자 ?? 해서 열심히 찾아봤더니 DP(동적계획법) 의 Hello World 와 같은 문제라고 한다 

강의를 듣자마자 바로 풀수 있었을 문제는 아닌것같고 .. 아무튼 유투부 보면서 보고 써본수준 (풀었다고 하기도 민망)

 

youtu.be/YHZiWaL49HY

이 영상 봤다 

 

DP 나 DFS 를 풀기위해선 점화식이 필요하다 

점화식이란 ? 규칙성 이라고 생각하면 될듯 그리고 보통 점화식은 제일 마지막 연산을 생각해보면 된다고 한다

 

이 문제의 규칙성은

이렇게 된다고 한다 (이걸 사람들은 어떻게 알았을까)

 

최종 소스는 이렇게 된다 

def dp(n):
    if n == 1:  #1인경우의 개수는 1개
        return 1
    elif n == 2: #2인 경우의 개수는 3개
        return 3 #점화식이 2(n-2) 라고 2개가 아님
    return dp(n-1)+2*(dp(n-2))
    
testCase = int(input())
for i in range(testCase):
    n=int(input())
    print('#'+str(i+1)+' '+str(dp(n//10)))

 

dp 문제를 많이 풀어봐야겠다 ㅜㅜ 아직은 이해가 잘 안됨