https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 중간에서 만나는 투 포인터를 이용하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; vector ph; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; ..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net vector candy(1000001, 0); ([사탕의 맛] = 개수)을 세그먼트 트리를 통해 나타냈고, 이분 탐색을 통해 원하는 사탕 순위를 만족하는 사탕의 맛을 구한다. 코드 #include #include #include using namespace std; int n; vector candy(1000001, 0); //[사탕의 맛] = 개수 vector sgmtt(..

https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [x위치][y위치][부순 벽의 개수][낮인지 밤인지]를 고려한 bfs를 통해 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n, m, k; vector board; int dxdy[5][2] = { {0,0},{0,-1},{-1,0},{0,1},..

https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 0번 정점이 루트인 트리를 만들고 트리를 만들면서 sub_tree_node[here]에 here가 루트인 서브 트리의 노드의 개수를 저장하고, result에는 0번 정점에서부터 각 정점으로 가는 비용을 저장한다. 그리고 루트에서 연결된 정점들 부터 Solve(int before, int here, int before_here_cost) (before : 부모 노드(이전 노드)..

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net int Solve(int police1_last, int police2_last) (police1_last는 경찰차1이 마지막으로 처리한 사건, police2_last는 경찰차2가 마지막으로 처리한 사건)으로 그때 최소 이동거리를 다이나믹 프로그래밍을 이용해 구하고, Police_check(int police1_last, int police2_last) (police1_la..

https://www.acmicpc.net/problem/13561 13561번: House Rental Your program is to read from standard input. The input starts with a line containing two integers k (1 ≤ k ≤ 100, 000) and n (k ≤ n ≤ 1, 000, 000), where n is the number of facilities along the main street and k is the number of different facility www.acmicpc.net map을 이용한 투 포인터를 이용하여 문제를 해결했다. 이때 두 포인터의 합이 음수이고, 그때 합의 절댓값이 홀수 일 때 와 같은 경우..