17425. 약수의 합
https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 어떤 수 \( x\) 의 약수의 합을 구하는 함수를 \( f(x)\) 라 하자. \( x\)보다 작거나 같은 수들의 약수의 합들을 모두 더한 수를 구하는 함수를 \( g(x)\)라 하자. \( g(x) = \sum_{k=1}^x f(k) \) 자연수 \( N\)이 주어졌을 때, \( g(N) \)을 구하는 문제이다. naive한 방법으로 문제..
14003 가장 긴 증가하는 부분 수열 5
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 수열의 최대 크기가 1,000,000 인 LIS 문제이다. LIS 의 크기만 구하는 문제가 아닌, 정답이 될 수 있는 LIS 하나 출력하는 문제. \( O(NlogN) \) LIS 알고리즘 (이분탐색) + 넣을 때마다 인덱싱 저장으로 문제를 해결할 수 있었음. /* 수정 중 */ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..
1208 부분수열의 합 2
https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열의 합 1 문제에서 사이즈만 다른 문제. 부분수열의 합 1 문제에서는 \( 1 second; return; } dfsR(pos+1, sum+v[pos], v, mp); dfsR(pos+1, sum, v, mp); } int32_t main() { cin.sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); c..
