사용 언어 - Python3
문제 - 01타일
정답
DP 기초 문제 (정답 맞춘 여부 X)
1. dp = [0]*(1000001), n+1 만큼 0으로 이루어진 리스트 dp 생성
2. 예외처리
n이 1,2이면, 답이 정해져있다. 가독성을 위해 인덱싱은 1부터 한다.
dp[1] = 1
dp[2] = 2
3. n이 3이상인 경우
dp[i] = i까지의 최대값
dp[i]=(dp[i-2]+d[i-1])%15746
dp[n] = 모든 2진 수열의 개수를 15746으로 나눈 나머지 <-- 정답
n = int(input())
dp = [0]*1000001
dp[1],dp[2] = 1, 2
for i in range(3,n+1):
dp[i] = (dp[i-1]+dp[i-2])%15746
print(dp[N])
레퍼런스
- 정답 참고
- 정답 깃허브
'Algorithm > 동적계획법' 카테고리의 다른 글
[프로그래머스 lv 4] 사칙연산 (0) | 2023.06.07 |
---|---|
[프로그래머스 lv 3] 등굣길 (0) | 2023.06.02 |
[프로그래머스 lv 3] 정수 삼각형 (0) | 2023.06.02 |
다이나믹 프로그래밍? (0) | 2023.06.01 |
[Python3] 백준 2579번 계단오르기 (0) | 2023.04.05 |
댓글