https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 역들의 관계로 그래프를 만들고, 직전에 방문했던 위치는 방문하지 않는 dfs를 수행하여, SCC(강한 연결 요소)를 만드는 것과 비슷한 방법으로, 사이클에 속한 정점들을 판별했다. 그리고, 각 정점(역)에서 사이클(순환선)까지 최단 거리는 해당 정점에서 사이클까지 bfs(너비 우선 탐색)를 수행하여 문제를 해결했다. 코드 #include #include #include ..

https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 사용한 파랑 페인트 수는, 어떠한 반지름의 원을 그린 상황에서 사용한 빨강 페인트양을 알면, 사용한 파랑 페인트양을 알 수 있다는 것을 이용했는데, 예를 들어 파랑 페인트 수는 n번째 원을 그린 상황에서 "n*(n+1)/2 - 사용한 빨강 페인트" 만큼 사용했다는 것을 알 수 있다. 이를 이용해 cache에 cache[반지름 크기][사용한 빨강 페인트] = "해당 반지름 크기의 헬기 착륙장을 정확히 사용한 ..

https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 지표면에 떨어지는 별똥별의 수를 최소화하기 위해, 트램펄린 모서리에 별이 위치해야, 많은 별을 튕겨낼 수 있다. 이를 위해, 별을 많이 튕겨낼 수 있는 경우인, 기존 별의 위치와 별 사이의 교차 지점을 기준으로 트램펄린을 펼치는 방법으로 문제를 해결했다. 코드 #include #include #include using n..

https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE > n; for (int i = 0; i > e >> x; if (range.count(e) == 0) { range.insert(make_pair(e, 1)); } else { range[e] += 1; } if (range.count(x) == 0) { range.insert(make_pair(x, -1)); } else { ..

https://www.acmicpc.net/problem/2465 2465번: 줄 세우기 첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열 www.acmicpc.net 키 순위에 대해 해당 키 순위의 키가 몇 개 있는지 rank_cnt에 rank_cnt[키 순위] = 해당 키의 개수 형식으로 저장해 놓고 이를 이용한 합 세그먼트 트리 sum_sgmtt를 만든다. 그리고, 수열 s의 마지막번째부터 어떤 순위에 속하는지 이분 탐색을 통한 세그먼트 트리 쿼리를 통해 찾아내는 과정을 통해 문제를 해결했다. 코드 #include #include #inc..

https://www.acmicpc.net/problem/16930 16930번: 달리기 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 www.acmicpc.net bfs(너비 우선 탐색)을 이용하는데, 움직이려는 방향의 k개만큼 모두 이동하는 게 아닌, 움직이려는 방향으로 1~k 칸을 확인해 나아가다가, 만약 확인하는 위치가 이전에 이미 현재 이동하는 것보다 더 빠른 길로 도착한 경우, 그쪽 방향의 확인은 이전에 도착한 경우에 맡기면 되기 때문에, 그쪽 방향은 더 이상 확인하지 않는 방법으로 문제를 해결했다. 코드 #include #include..