[DP/동적계획법] 백준 1788 피보나치 수의 확장 - 파이썬(Python)
[ Contents ] 1. 문제 (링크 참조) 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 피보나치의 '음수 부분'을 구하는 문제입니다. 본래, 피보나치는 n = 2부터 시작하죠. n = 1일 때, f(1) = f(0) + f(-1) 이므로 f(-1) = f(1) - f(0) = 1 피보나치의 정의를 역이용하면, f(-1)도 구할 수 있습니다. 즉, 음수 부분을 구할 때에는 조금 식이 달라집니다. f(n-2) = f(n) - f(n-1) f(-1) = f(1..
2022. 8. 30.
[동적계획법/DP] 백준 9184 신나는 함수 실행 - 파이썬(Python)
[ Contents ] 1. 문제 (링크 참조) 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 2. 문제 풀이 if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) ..
2022. 6. 30.
