0850

문제: https://www.acmicpc.net/problem/12015난이도: G2 가장 긴 증가하는 부분 수열의 길이만 구하는 문제라면 그리디한 풀이와 이분탐색으로 구할 수 있다. 모든 값에 대해 아래 과정을 반복한다. 1. vector가 비어있거나 가장 마지막 값보다 큰 수면 push_back2. vector에 있는 수라면 넘어감3. 1과 2가 아니라면 그 수보다 가장 가까운 큰 수와 대체 3을 구할 때 이분 탐색의 upper_bound로 구할 수 있다. 그리고 2는 upper_bound의 index에서 -1한 값이 같은지 아닌지 확인하면 된다.#include #include using namespace std;vector v;int main() { ios::sync_with_stdio(false..

문제: https://www.acmicpc.net/problem/7579난이도: G3 배낭문제의 일종으로 기계오리연구(https://www.acmicpc.net/problem/28082)와 유사한 문제이다.dp[i]: i의 비용으로 확보할 수 있는 최대 메모리 용량이다. N과 비용이 0~100이므로 O(100*10000)의 시간복잡도로 풀 수 있다. dp[10001]을 모두 구한 후, 그중 M 이상을 값을 가지는 비용 중 최소가 답이다. #include #include using namespace std;int dp[10001];vector a;vector m;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); in..