득이공간

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net #include #include #include using namespace std; const int DX[4] = { -1, 0, 1, 0 }; const int DY[4] = { 0, -1, 0, 1 }; int N, M; bool Wall[1000][1000]; bool Visited[1000][1000]; int Area[1000][1000]; int AreaSize[1000000]; int BFS(int AreaNum, int SR..

10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net #include using namespace std; bool LandingGate[100001]; int Root[100001]; int Find(int Node) { if (Node == Root[Node]) { return Node; } return Root[Node] = Find(Root[Node]); } void Union(int NodeA, int NodeB) { int A = Find(NodeA); int B = Fi..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net #include #include using namespace std; typedef pair p; int Seq[5000000]; priority_queue PQ; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, L; cin >> N >> L; for (int i = 0; i > N..

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..