[ BOJ / Python ] 2688번 줄어들지 않아
이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 전에 자릿수로 만들 수 있는 수를 만드는 문제를 풀어본 기억이 나서 점화식을 쉽게 구할 수 있었다. 점화식을 구하기 위해 도식화 해보았다.
전에 구했던 점화식과 조금 다른 점화식을 도출할 수 있었다. 전에 구했던 점화식은 dp[i][j]
를 구하기 위해 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j]
를 사용했었다. 이번에는 더 간단한 패턴을 발견하였다. 이 점화식의 응용이기도 하다. dp[i][j-1]
는 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]
의 값이 될 것이다. 그러므로 dp[i][j]
는 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j] = dp[i][j-1]+dp[i-1][j]
가 된다.
점화식
dp[i][j] = dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]+dp[i-1][j]
= (dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1])+dp[i-1][j]
= dp[i][j-1]+dp[i-1][j]
이렇게 dp리스트에 메모라이제이션을 진행해주고, dp[n]
의 전체 값의 합을 구하면 결과값이 된다. 처음에 작성하였을 때에는 dp[n]
의 값이 dp[n+1][9]
의 값과 같아서 n보다 1번 더 dp리스트를 채우고 구하는 방식으로 구현했었다. 그러나 sum()함수로 sum(dp[n])
을 구하는 것이 더 깔끔할 것 같다는 생각이 들어서 코드를 수정하였다.
- t를 입력받는다.
- t번 반복하는 for문을 돌린다.
-> n을 입력받는다.
-> dp 리스트를 (n+1)*10의 크기에 0을 채워 선언한다.
->dp[0][0]
을 1로 갱신한다.
-> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
--> 10번 반복하는 j에 대한 for문을 돌린다.
--->dp[i][j]
를dp[i-1][j]+dp[i][j-1]
의 값으로 갱신한다. dp[n]
의 총 합을 출력한다.
Code
t=int(input())
for _ in range(t):
n=int(input())
dp=[[0]*10 for _ in range(n+1)]
dp[0][0]=1
for i in range(1, n+1):
for j in range(10):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(sum(dp[n]))
t=int(input())
for _ in range(t):
n=int(input())
dp=[[0]*10 for _ in range(n+1)]
dp[0][0]=1
for i in range(1, n+1):
for j in range(10):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
print(sum(dp[n]))
Author And Source
이 문제에 관하여([ BOJ / Python ] 2688번 줄어들지 않아), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-2688번-줄어들지-않아저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)