www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 트리를 만들고 트리 DP(트리에서의 다이나믹 프로그래밍)를 이용해서 문제를 해결했는데, 100000(n의 최댓값)은 2의 16.xx승 이므로 18개의 색깔이면 충분하다는것을 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector adj[100001]; int cache[100001][19]; //100000은 ..

www.acmicpc.net/problem/1637 1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 이분 탐색을 이용해서 mid숫자까지 전체 개수 누적합을 구하고, 전체 개수 누적합이 홀수 이면 홀수개 존재하는 정수가 1~mid사이 범위 안에 존재하는 것을 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector a; vector c; vector b; //number까지..

www.acmicpc.net/problem/13344 13344번: Chess Tournament Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is www.acmicpc.net 유니온 파인드를 이용하여 같은 능력의 플레이어는 묶는다. 그리고 묶은 집합을 이용하는데, 이기는 쪽으로 이동하는 집합으로 가는 집..

www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 유니온 파인드를 이용해서 문제를 해결했다. 그런데 시간 초과를 해결하기 위해, 쿼리에서 전체 에지(n-1개)를 모두 제거하므로 정점이 모두 분리 되있는 경우부터 거꾸로 생각해 나간다. 즉 거꾸로 가면서 에지를 제거하는 쿼리는 에지를 연결하는 식으로 진행한다 그리고 거꾸로 진행했으므로 결과도 뒤집는다. 코드 #include #include #include #include using name..

www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net to_from에 ((목적지, 출발지),박스의 개수)를 저장하여 목적지, 출발지 순으로 정렬하고 목적지가 빠른 것부터 현재 택배를 옮기는 구간에서 가장 많이 택배가 쌓여 있을 때를 구해서 트럭에 최대한 쌓을 수 있는 개수를 구한 뒤, 트럭에 최대한 쌓을 수 있는 개수가 택배의 개수보다 작을 때는 지금 택배 개수 전체를 넣을 수 없고, 그렇지 않을 때는 지금 택배 개수 전체를 넣을 수 있다는 것..

www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 제일 아래쪽에 모두 미네랄이 있다고 생각하고 문제를 해결했다. 이유는, 공중에 뜬 클러스터를 확인하기 위해, 바닥에 붙어 있는 클러스터를 체크했는데, 이때 제일 아래쪽(모두 미네랄이 있다고 생각한 곳)에서 탐색을 진행해서 바닥에 붙어 있는 클러스터들을 체크했기 때문이다. 코드 #include #include #include #include #include using namespace std; int r, c; int ..