득이공간

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #include #include using namespace std; int Sequence[1000]; int DP[1000]; stack LIS; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int Max = 0; int Index = 0; int N; cin >> N; for (int i = ..

18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net #include using namespace std; int Factory[10002]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > Factory[i]; } int Price = 0; for (int i = 0; i < N; ++i) { int Num; ..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net #include #include #include using namespace std; list Neighbor[32001]; int Entry[32001]; priority_queue PQ; list Sorted; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; for (int i = 0; i <..

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net #include #include #include using namespace std; typedef long long ll; typedef pair jewel; jewel Jewel[300000]; int Bag[300000]; priority_queue PQ; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ..

20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net #include using namespace std; typedef pair team; int N, M, K; int Candy[30000]; int Root[30000]; bool Visited[30000]; int TeamNum; team Team[30000]; int DP[30001][3001]; int Find(int Node) { if (Node == Root[Node]..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net #include #include using namespace std; int N, Cnt; int Student[100000]; bool Visited[100000]; bool Check[100000]; void DFS(int Current) { Visited[Current] = true; int Next = Student[Current]; if (!Visited[Next]) { DFS(Next); } else if (!Check[Next]) { for (int i ..

7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net #include using namespace std; int Memory[101]; int Cost[101]; int DP[101][10001]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; for (int i = 1; i > Memory[i]; } for (int i = 1; i > Cost[i]; } for (int i = 1..

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string Origin; cin >> Origin; stack Operator; for (int i = 0; i = 'A') { cout

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net #include #include #include using namespace std; int N; list Neighbor[100000]; bool Visited[100000]; int Max; int A, B; void DFS(bool bFindA, int Idx, int Length) { Visited[Idx] = true; int Cnt = 0; for (const pair& N : Neighbor[Idx]) { if (!Visited[N...

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net #include #include #include using namespace std; typedef pair p; typedef pair pp; const int DX[4] = { -1, 0, 1, 0 }; const int DY[4] = { 0, -1, 0, 1 }; int N; int Bowl[20][20]; bool Visited[20][20]; int Time, Ate; int Size = 2; int Row, Col; bool Target(int ..