엘릭시르제

1. 동전 (BOJ 9084)dp, knapsack 동전 하나를 잡고 그 동전의 값 이상부터 n까지 이전 값을 불러오면 된다. 당연히 0원은 무조건 만들 수 있으니 1로 초기화 해서 시작하면 된다. 2. 겹치는 선분 (BOJ 1689)sweeping, sorting imos법 같이 돌리면 된다. 즉, 시작 점은 1로 두고, 끝 점은 -1로 둬서 점의 위치를 중심으로 정렬해준다.예를 들어 (1, 5), (3, 6), (2, 3)가 있으면 (1, 1), (2, 1), (3, -1), (3, 1), (5, -1), (6, -1)로 될 것이다. 그리고 좌표 하나하나씩 순서대로 확인해서 변수에 +1, 혹은 -1을 하고 최댓값을 갱신하면 된다. 당연히 -1이 1보다 작으므로 먼저 계산되기 때문에 '선분의 끝 점에서..

문제 링크: https://www.acmicpc.net/problem/32454 문제 풀이피사노 주기, 오일러 피 함수, 분할 정복을 이용한 거듭제곱 일단 $7^{7^{7^n}}$을 먼저 보면 벌써부터 답이 없어지는데, 이 수는 매우 크기 때문에 사실상 직접 구하는 것은 불가능하다. 그래서 접근하기가 힘든데, $7^{7^{7^n}}$번째 피보나치 수를 $10$번째 자리까지 출력하라고 적혀있다. 이 말은 피보나치 수를 구했을 때 $10^{10}$으로 나눈 값만 구하면 된다. 그렇다면 여기서 떠올리는 게 있다면 쭉쭉 풀려질 것이다. 피사노 주기를 이용하면 된다. 피보나치 수에서 나누는 값이 $10^{m} (m > 2)$라면 주기는 $15 \times 10^{m-1}$다. $m = 10$이므로 주기는 $15 ..