1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
문제풀이:
dp[0] = [1,0]
dp[1] = [0,1]
dp[i][0] = dp[i-1][0] + dp[i-2][0]
dp[i][1] = dp[i-1][1] + dp[i-2][1]
이미 구해놓은 수열은 반복하여 구하지 않고 바로 출력할 수 있도록 idx를 매번 업데이트 해주었다.
import sys
T = int(sys.stdin.readline())
dp = [[0,0] for _ in range(41)]
dp[0] = [1,0]
dp[1] = [0,1]
idx = 2
for _ in range(T):
N = int(sys.stdin.readline())
for i in range(idx,N+1):
dp[i][0] = dp[i-1][0]+dp[i-2][0]
dp[i][1] = dp[i-1][1]+dp[i-2][1]
idx = max(idx,N+1)
print(dp[N][0], dp[N][1])
'알고리즘💻 > DP' 카테고리의 다른 글
BOJ 1932번: 정수 삼각형 (0) | 2021.08.01 |
---|---|
BOJ 1149번: RGB거리 (0) | 2021.05.05 |
BOJ 13301번: 타일 장식물 (0) | 2021.05.05 |
BOJ 17626번: Four Squares (0) | 2021.03.23 |
BOJ 12865번: 평범한 배낭 (0) | 2021.01.24 |