목록1003 파이썬 (1)

Gemstone's Devlog

[백준] 1003번: 피보나치 함수 (다이나믹 프로그래밍)

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 이 문제는 규칙성을 이용하는 DP 문제이다. 우선 그림을 한 번 그려보자. N에 따라서 0과 1이 어떻게 되는지 보자. 이 규칙성을 가지고 DP를 사용하여 구현하면 풀이는 다음과 같다. t = int(input()) for _ in range(t): cnt_0 = [1, 0] cnt_1 = [0, 1] n = int(input()) if n > 1: for i in range(n - 1): cnt_0.append(cnt_1[-1]) cnt_1.append(cnt_0[-2] + cnt_1[-1]..
Data Structure & Algorithms 2022. 4. 4. 10:19
이전 Prev 1 Next 다음