레야몬

1. 문제 N개의 물건과, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오. - 1 - \(N, C(1 \leq N \leq 30, 0 \leq C \leq 10^{9}\) - 2 - \(w(1 \leq w \leq 10^{9})\) 가방에 넣는 방법의 수 2. 재정의 C이하의 부분 수열의 합의 개수 3. 해결방법 수열의 반으로 쪼갠 후 부분 수열의 합을 모두 구한다. 그리고 이를 v1, v2에 저장한다 v2를 탐색하면서 C - v2의 값보다 작거나 같은 v1의 원소의 수만큼 cnt를 더하고 이를 출력한다. 4. 실수한 점, 개선할 점 \(10^{9} \times 30\)은 int형 범위를 넘어갈 수 있다. lower_bo..

1. 문제 N * N 크기의 배열 A[i][j] = i * j이다. 이를 배열 B에 넣으면 크기는 N * N이 된다. B를 오름차순 정렬했을 때 B[k]를 구해보자. A, B의 인덱스는 1부터 시작 - 1 - 배열의 크기 \(N(1 \leq N \leq 10^{5}\) - 2 - \(k(1 \leq k \leq min(10^{9}, N^{2})\) B[k] 2. 재정의 A[i][j] = i *j일때 이들의 오름차순 순서를 구하시오. 3. 해결 방법 이 프로그램의 목표는 k번째 숫자인 mid를 찾는 것이다. cnt(mid)를 통해 mid 아래에 몇 개의 숫자가 있는지 확인하며 cnt(mid) = k이면 hi = mi..

#include #include #include #include #define LOOP(i, N) for(int i=1; i> N; LOOP(i, N) { int x, id; cin >> x; if(x>num.back()) { num.push_back(x); //제일 큰 숫자 seq[num.size()-1].push_back(x); } else if((num[id = (lower_bound(num.begin(), num.end(), x) - num.begin()) ])!=x) { num[id]=x; seq[id].push_back(x); //갱신 된 결과를 벡터에 추가하기 } } cout

#include #include #include #define LOOP(i, N) for(int i=1; i> N; LOOP(i, N) { int x; cin >> x; if(x>num.back()) num.push_back(x); else num[lower_bound(num.begin(), num.end(), x) - num.begin()]=x; } cout