블로그 언저리인 무언가

문제 : 10165 버스노선 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 원형으로 이루어진 버스 노선들 중에서 다른 노선에 포함되어있는 노선들을 제거한 후 출력하는 문제이다. 일단 원형노선을 알아보기 쉽게 일자로 펴기 위해서 0을 지나는 노선 들 중 가장 출발점이 앞선 것 기준으로 다시 정렬을 해주고 출발점 기준으로 찾으면서 도착점이 현재 최대 도착점보다 짧은 노선들을 제거 한 후 노선들을 정렬해 출력해주면 된다. Code #include #define ll lon..

문제 : 2873 롤러코스터 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 롤러코스터가 갈 수 있는 칸이 주어지고 이를 지나면서 가장 최대의 행복값을 가지도록 경로를 구현하는 문제이다. 기본적으로 홀*홀, 짝*홀, 홀*짝 경우에서는 ㄹ자로 순회하면 모든 칸을 지날 수 있으므로 행이나 열이 홀수인 방향을 찾아 모든 칸을 지나도록 경로를 만들어 출력하면 된다. 결국 이문제의 문제는 짝*짝 상황에서 어떻게 최댓값을 찾아내냐는 것인데 어찌어찌 머리를 굴리다 보면 [짝, 홀] 칸이나 [홀, 짝] 칸 하나만 지나지..

문제 : 20041 Escaping 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 도둑의 좌표가 주어지고 경찰의 좌표가 주어졌을 때 도둑이 영원히 도망칠 수 있는지 확인하는 문제이다. 기본적인 아이디어로는 도둑이 도망치는게 가능하다고 할때 굳이 지그재그로 갈 필요없이 위, 아래, 오른쪽, 왼쪽 중에서 한방향을 정해 쭉 달리면 된다는것을 알수 있고 이를 이용해 위, 아래, 오른쪽, 왼쪽 모두에 경찰이 존재할때만 도망치는것이 불가능함을 알수있다. 여기에서 현재 경찰이 있는 점이 ..

문제 : 3321 가장 큰 직사각형 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net 기본적으로 1로 채워진 가장 큰 정사각형을 찾는 문제이지만 열의 순서를 바꿀 수 있으므로 결국 각 행에 대해서 열의 높이를 정렬하여 누적합을 이용하면 행의 길이를 1씩 늘려가면서 최대 넓이를 구할 수 있다. 이를 구현하게 되면 총 행의 개수 N번, 각 행을 정렬하는데 걸리는 시간이 퀵 정렬 사용 시 MlogM이므로 시간 복잡도가 O(NMlogM)이 되는데 시간제한이 0.6초이기 때문에 이를 O(NM)으로 줄여야 한다. 나 같은 경우에는 deque를 사용해 정렬 시간을 ..

문제 : 2573 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙산의 위치와 높이가 주어질 때, 2개 이상으로 나누어지는 시간을 구해 출력하는 문제이다. 매해 빙산이 녹는 높이를 카운트해서 줄여주면서 BFS를 통해 빙산의 개수를 구해 0이나 2 이상이 되는 순간을 출력하면 된다. Code #include #define ll long long using namespace std; typedef pair pll; ll N, M, ans, arr[305][305], cnt[305][305], visi..

문제 : 1916 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 도시의 개수와 도시들 간에 운행하는 버스의 비용이 주어졌을 때 최소비용으로 이동하는 금액을 출력하는 문제이다. 다익스트라 알고리즘을 이용해서 해결하면 최소비용을 쉽게 구할 수 있다. Code #include #define ll long long #define INF 1e9+7 using namespace std; struct ABC{ ll idx, dst; ABC() {} ABC(ll idx, ..

문제 : 9375 패션왕 신혜빈 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 의상의 수와 이름이 주어졌을 때 맨몸이 아니도록 옷들의 조합의 수를 찾아서 출력하는 문제이다. 같은 의상의 종류를 센 후 +1씩 해서 곱해 전체 조합의 수를 세고 하나도 입지 않는 것은 불가능하므로 1을 빼서 출력하면 된다. Code #include #define ll long long using namespace std; ll N; ma..