본문 바로가기

PS - 알고리즘64

13215 - Fish step 1더보기N개의 세그먼트가 있다고 해봅시다. 저희가 이미 어떤 방법을 통해서 [1, N/2], [N/2+1, N] 영역에 대해 답을 구했다고 해봅시다. 그럼 이 두 영역에 모두 걸쳐있는 영역에 대해 답을 구하면 문제를 해결할 수 있습니다.step 2더보기[1, N/2] 영역에서 오른쪽 부분합과 [N/2+1, N] 영역의 왼쪽 부분합을 구합니다. 오른쪽 부분합은 영역의 오른쪽 부터 왼쪽으로 쭉 진행하면서 나온 값들을 쭉 더해온 값입니다. 왼쪽 부분합은 왼쪽부터 진행한 것입니다. 이 부분합들을 각각 정렬합니다. 그리고 투포인터를 이용하면 두 영역에 모두 걸쳐있는 영역의 답을 구할 수 있습니다.분할정복으로 두 영역에 대해 답을 구하고 투포인터로 합쳐주면 됩니다.코드더보기#define _CRT_SECUR.. 2024. 10. 21.
11025 - 요세푸스 문제 3 step 1더보기메모리 제한이 16mb입니다. 이거는 배열이나 세그 트리 같은 것을 사용하지 않고 풀라는 이야기입니다.(N, K)-요세푸스 순열의 답을 알고 있다고 해봅시다. (N+1, K)-요세푸스 순열은 무엇일까요?step 2더보기예시에 있는 경우를 생각해 봅시다. 한 사람이 제거될 때 까지 진행한 다음 순서와 숫자를 조금 섞어주면 다음과 같이 됩니다.(6, 3) 요세푸스 순열의 답은 1입니다. 그럼 이 과정을 반대로 올라간다고 생각하면 (7,3) 요세푸스 순열은 4임을 알 수 있습니다.(1, K) 요세푸스 순열의 답은 1입니다. 여기서부터 거꾸로 올라가면서 생각하면 쉽게 답을 구할 수 있습니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#includ.. 2024. 10. 14.
23755 - 카드컨트롤 (Hard) step 1더보기위에서부터 셌을 때 준석이는 홀수번째 카드, 수현이는 짝수번째 카드를 가져갑니다. 홀수번째에 있는 O의 개수가 더 많으면 준석이가 이깁니다.만약 처음부터 준석이가 이긴다면 답은 0입니다.만약 처음부터 수현이가 이긴다면 답은 1입니다. 제일 밑 카드를 위로 올리면 홀짝이 바뀌면서 승패도 바뀌게 됩니다.무승부일때(홀수 번째의 O와 짝수 번째의 O의 개수가 같은 경우)만 처리를 하면 됩니다.step 2더보기위에서부터 2개씩 짝을 지어 봅시다. 그럼 OO, OX, XO, XX 4종류가 나옵니다. OX는 준석이가 이기는 경우, XO는 수현이가 이기는 경우입니다.홀수 번째의 O와 짝수 번째의 O의 개수가 같기 때문에 OX의 개수와 XO의 개수가 같습니다.만약 XO가 하나라도 있는 경우 X를 먼저 올.. 2024. 10. 7.
24520 - Meet In The Middle step 1더보기신촌 왕국은 트리 구조로 되어 있습니다. 두 사람의 위치가 s, e라고 하겠습니다. 1번 영역은 항상 s가 더 가깝습니다.2번 영역은 항상 e가 더 가깝습니다.만약 초록색 점이 답이라고 가정하면 빨간 점이 각 마을까지 거리의 합이 더 짧으므로 모순이 생깁니다.즉, s와 e 사이의 경로에 답이 있습니다.step 2더보기LCA를 이용해서 두 점 사이의 거리를 구할 수 있습니다. 그리고 LCA를 이용해서 s나 e에서 특정 거리만큼 떨어진 경로 위의 점을 구할 수 있습니다.LCA를 구할 때 dfs로 하면 메모리가 터질 수 있습니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#include#includeusing namespace std;vecto.. 2024. 9. 30.
10479 - 따르릉 따르릉 step 1더보기맥스를 반지름이 0.5인 원으로 생각하면 조금 복잡합니다. 사람을 점으로 표현할 수 있는 방법이 없을까요?맥스의 중심을 기준으로 자동차의 빨간 원 안에 들어가면 차와 충돌하게 됩니다. 차 부분만 확대하면 다음과 같습니다.0.5만큼 살찌웠다고 생각하면 됩니다. 그럼 맥스에 해당하는 점이 자동차 주위 빨간 영역과 겹치는지 확인하면 됩니다.step 2더보기지금부터 자동차를 고정시킬 것입니다.맥스는 위로 M의 속도로, 차는 오른쪽으로 B의 속도로 달립니다.그럼 이건 차가 고정되어 있고 맥스가 위로 M, 왼쪽으로 B의 속도로 달리는 것과 같습니다. 맥스는 t초 뒤에 출발합니다. 그 말은 맥스가 처음 위치에서 Bt미터 왼쪽에서 출발한다는 것과 같습니다. 그럼 자동차 입장에서 맥스가 어떻게 움직이는지.. 2024. 9. 23.
1314 - 동굴 탐험 step 1더보기$N+1$개의 비트로 이루어진 2진수를 생각합니다. $i$번째 비트가 0이면 i번째 사람이 왼쪽에 있다는 뜻이고 1이면 오른쪽에 있다는 뜻입니다. $N+1$번째 비트는 지도의 위치입니다. 0이면 지도가 왼쪽, 1이면 오른쪽에 있다는 뜻입니다.step 2더보기$N$개의 비트로 이루어진 또 다른 2진수를 생각합니다. 자신에 해당하는 비트가 1인 사람들이 함께 움직입니다. $1010_{(2)}$면 2, 4번 사람이 함께 움직입니다.믿을 수 있는 사람이 없다거나 무게가 넘어서 건널 수 없는 경우가 있습니다. 1부터 $2^N-1$까지 모든 경우에 대해 이동이 되는지 안되는지 구해 둡니다.step 3더보기처음 생각한 $N+1$개의 비트로 이루어진 2진수를 정점으로 생각합니다. 이동이 가능한지, 그때.. 2024. 9. 16.

티스토리툴바