본문 바로가기

백준

 (223)
백준 16681 - 등산 https://www.acmicpc.net/problem/16681 힌트 더보기 집 -> 어떤 지점 방향으로는 올라가고 어떤 지점 -> 고려대학교 방향으로는 내려간다... 여기서 어떤 아이디어를 떠올릴 수 있겠는가? 풀이 더보기 어떤 지점 $X$를 기준으로 내려가야 되는 경로와 올라가는 경로가 다르다. 이를 살펴보면 $X$에서 고려대학교까지 내려가는 것은 고려대학교에서 $X$까지 올라가는 것과 같다. 따라서 다음과 같은 아이디어를 생각할 수 있다. 1. 집에서 올라가는 최단 경로 $sp_{1, x}$들을 계산한다. 2. 고려대학교에서 올라가는 최단 경로 $sp_{2, x}$들을 계산한다. 3. 어떤 지점 i에서 $sp_{1, i}$ 와 $sp_{2, i}$가 존재하면 i를 기준으로 문제 조건에 맞는 등산..
백준 4160 - 이혼 https://www.acmicpc.net/problem/4160 힌트 더보기 브루트 포스를 시행하면 $3^{24}$만큼 경우의 수가 있다. 밋 인 더 미들을 통해 $O(3^{12})$로 풀 수 있다. 풀이 더보기 다음 3가지를 한 번에 고려해보자. 잭이 가지는 집의 가치 질이 가지는 집의 가치 판매하는 집의 가치 3가지를 각각 따져서 브루트 포스로 잭의 집 가치와 질의 집 가치가 같은 경우를 찾으면 $3^{24}$만큼 경우의 수가 나오고 이는 매우 커서 30초라는 제한 시간 안에 어림도 없음을 알 수 있다. 밋 인 더 미들을 기법을 사용해 주어진 집을 2개의 부분 집합으로 쪼개자. 그러면 각 집합의 크기는 최대 12가 된다. 이때 우리는 다음을 구할 것이다. 분할된 집합을 각각 $s_{1}$, $s_{..
백준 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 https://www.acmicpc.net/problem/20440 선분 imos법을 통해 모기들의 증감을 관리하여 밀도가 가장 높으면서 긴 구간을 출력하면 된다. 다만 imos법을 사용하면 한 곳에서 여러마리의 모기가 들어왔다 나갈 수 있으므로 가장 긴 구간을 구하기 위해 각 지점에서 발생하는 모기의 출입을 하나의 pair로 합쳐줘야 한다. 본인은 unordered_map을 사용하여 이를 간단히 처리했다. 그 후 다음 과정을 거친다. 1. 모기의 출입을 정리한 후 구간을 스위핑 하면서 현재 저장한 최댓값보다 더 높은 값을 찾았을 때 start를 해당 구간의 시작점, end를 -1로 초기화 한다. 2. 이전까지 모기의 밀도가 최대고 현재 지점의 밀도가 최댓값보다 작아졌을 때 end가 -1이라면 end를 ..
[ICPC] 백준 5419 - 북서풍 https://www.acmicpc.net/problem/5419 힌트 더보기 문제에서는 남동쪽 방향으로 가라고 하지만 조건을 생각하면 북서쪽 방향으로 간다고 해도 동일한 결과를 얻을 수 있다. 어떤 섬에 도착했을 때 그 섬과 짝이 될 수 있는 섬의 개수를 효율적으로 셀 수 있겠는가? 이에 대해 감이 잘 오지 않으면 먼저 세그먼트 트리에 대해 공부한다. 풀이 더보기 구간 트리로 다음 구간을 관리한다. 해당 구간에 해당하는 좌표를 가진 섬이 출현한 횟수의 합 이렇게 되면 낮은 좌표를 가진 섬부터 구간에 반영하면서 해당 섬과 연결될 수 있는 섬의 개수를 세주면 가능하다. 그러면 좌표를 정렬해야 할 텐데 어떻게 정렬해줘야 할까? 문제를 보면 무조건 동남쪽 방향으로 섬을 이어야 할 것 같지만 달리 생각하면 북서..
[ICPC] 백준 9081 - 단어 맞추기 https://www.acmicpc.net/problem/9081 주의! 이 문제에는 낚시가 있다! 출력란에 써진 글을 보자. 각 테스트 케이스에 대해서 주어진 단어 바로 다음에 나타나는 단어를 한 줄에 하나씩 출력하시오. 만일 주어진 단어가 마지막 단어이라면 그냥 주어진 단어를 출력한다. 여기서 말하는 마지막 단어는 입력의 마지막이 아니라 사전순으로 마지막인 단어를 의미한다! C++의 경우 next_permutation()을 할 때 현재 순열이 사전순으로 마지막이라면 false를 반환한다. next_permutation의 결과가 false이면 prev_permutation으로 다시 되돌린 후 출력하면 된다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma ..

티스토리툴바