오늘의 문제 2일차 ~ 6일차 풀이
6일차 (장미) : 실버 I $a \times c$개의 장미를 살 때는, $\frac{b}{a}, \frac{d}{c}$ 중 작은 쪽의 장미를 사는 것이 무조건 이득입니다. 따라서, 장미 한 개당 가격이 높은 장미를 $a \times c$개 이상 사지 않습니다. 따라서 $\frac{b}{a} > \frac{d}{c}$라면 a의 한 개당 가격이 더 비싸니까, a개 짜리를 0묶음, 1묶음, ..., c-1묶음 사는 경우를 고려해주면 됩니다. 시간복잡도 : $\frac{b}{a} > \frac{d}{c}$이면 $O(c)$, $\frac{b}{a} j인 모든 (i, j)에 대해, dp[i][j]를 구해줍니다. 이분탐색으로 수열의 i번째 항 - j번째 항 = j번째 항 - m번째 항인 m을 찾으면, dp[i][j..
(BOJ 17372) 피보나치 수의 최대공약수의 합
https://www.acmicpc.net/problem/17372 17372번: 피보나치 수의 최대공약수의 합 첫 번째 줄에 구하는 합을 1,000,000,007로 나눈 나머지를 출력합니다. www.acmicpc.net 모바일 환경일 경우 수식이 깨질 수 있습니다. 수열 F가 $F_{1} = 1, F_{2} = 1, F_{n+1} = F_{n} + F_{n-1}$를 만족할 때, $\sum_{i=1}^{n}{\sum_{j=1}^{n}{gcd(F_{i}, F_{j})}}$ 를 구하는 문제입니다. 배경지식 gcd(a, b) : a, b의 최대공약수로, 자연수 a와 b를 모두 나누는 가장 큰 자연수입니다. $I$ : 자연수 n에 대해 f(n) = 1을 만족하는 함수입니다. $Id$ : 자연수 n에 대해 f(n..
