PS - 알고리즘64 29845 - Pipes 해석더보기$N$개의 파이프를 오른쪽에서 왼쪽으로 굴립니다. $i$번째 파이프의 반지름은 $r_i$입니다. 파이프를 다 굴렸을 때, 모든 파이프 중 벽으로부터 가장 먼 지점까지의 거리를 계산하세요step 1더보기시간복잡도를 무시하면 이 문제를 어떻게 풀 수 있을까요? $d[i]$ = 왼쪽에서 $i$번째 파이프가 벽에서 떨어진 거리$r[i]$ = 왼쪽에서 $i$번째 파이프의 반지름 이라고 합시다. $i$번째 파이프를 굴린다고 했을 때 이 파이프가$i-1$번째 파이프와 만날 때의 위치, $i-2$번째 파이프와 만날 때의 위치,...$1$번째 파이프와 만날 때의 위치, 벽과 만날 때의 위치를 전부 구하고 그 중 벽에서 가장 멀리 떨어진 지점이 답이 됩니다. 접하는 두 파이프의 반지름이 $r_1, r_2$일 때 .. 2025. 2. 10. 2244 - 민코프스키 합 step 1더보기다각형 A의 원점을 다각형 B의 한 꼭짓점으로 이동시켜 봅시다. 그때, 다각형 A가 차지하는 영역은 민코프스키 합에 포함됩니다. 이제 A의 원점을 B의 테두리를 따라 이동시킨다고 생각해 봅시다. 그때 A가 지나는 모든 영역은 민코프스키 합에 포함됩니다. 그리고 그 내부 역시 민코프스키 합에 포함됩니다. 다각형 A, B 둘 다 볼록다각형 1개로 이루어져 있으므로 이렇게 만들어진 영역 역시 볼록다각형입니다.step 2더보기모든 A의 꼭짓점 $(a_x, a_y)$과 모든 B의 꼭짓점 $(b_x,b_y)$에 대해 $(a_x+b_x, a_y+b_y)$를 계산합니다. 각 다각형은 최대 1000개의 꼭짓점을 가지므로 총 1,000,000개의 꼭짓점이 나옵니다.이 꼭짓점을 모두 포함하는 볼록다각형을 구.. 2025. 1. 20. 20121 - 카드 셔플 step 1더보기카드가 $N$장 있을 때 제일 위를 0번째 카드, 제일 밑을 $N-1$번째 카드라고 합시다. $X$셔플을 한번 하면 $X$번째 카드는 $(X*2)\%N$으로 이동합니다. $Y$셔플을 한번 하면 $X$번째 카드는 $(X*2+1)\%N$으로 이동합니다.step 2더보기처음 카드가 $X$번째에 있다고 가정합니다. 한 번의 셔플을 했을 때 카드는 $(X*2)\%N\sim (X*2+1)\%N$에 있을 수 있습니다. 한번 더 셔플을 하면 $(X*4)\%N\sim (X*4+3)\%N$에 있을 수 있습니다. 한번 할 때마다 있을 수 있는 위치가 2배씩 늘어납니다. 그럼 대략 30번의 셔플을 하면 모든 위치를 커버할 수 있습니다.만약 목표하는 위치를 커버하게 되면 이 과정을 역으로 올라가면서 어떤 셔플을.. 2025. 1. 13. 10919 - 선물상자 step 1더보기각 사람들한테 선물을 주었을 때 아만이 왼쪽으로 출발했는지 오른쪽으로 출발했는지 기록해 두었다고 가정합니다. 이렇게 했을 때 왼쪽과 오른쪽이 번갈아 가면서 나올 수 있을까요? 그 경우 순서를 바꿔서 더 최적인 상황을 만들 수 있습니다. 이것을 반복하다 보면 특정 위치를 기준으로 한쪽은 왼쪽, 다른 쪽은 오른쪽만 있게 됩니다. 이것을 왼쪽 사람과 오른쪽 사람으로 부르겠습니다. 그럼 모든 가능한 경계선에 대해 답을 구하면 쉽게 해결할 수 있습니다.step 2더보기사람들을 위치 기준으로 정렬합니다. 출발점에서 가장 멀리 떨어진 오른쪽 사람한테 선물을 준다고 생각해 봅시다. 그럼 나머지 선물은 2, 3,..., K번째 오른쪽 사람한테 줘야 합니다.dp-r[i]: i번째 사람이 가장 먼 오른쪽 사.. 2024. 12. 30. 18407 - 가로 블록 쌓기 step 1더보기특별한 아이디어를 사용하는 것은 아닌 것 같습니다. 그냥 이 알고리즘을 알면 풀 수 있고 모르면 풀 수 없는 문제입니다. 우선 좌표가 너무 크니 좌표 압축을 해줍시다. 이러면 최대 좌표가 최악의 경우 200000이 됩니다. 만약 레이지 세그먼트 트리에 대해 알고 있으면 이 문제를 쉽게 해결할 수 있습니다.step 2더보기세그먼트 트리에 "이 범위에 있는 블록 중 최대 높이"를 저장해 둡니다. 그리고 이번에 놓을 블록이 차지하는 범위 내에 있는 블록 중 최대 높이를 구합니다.그 값에 1을 더한 다음 값을 덮어씌웁니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include#includeusing namespac.. 2024. 12. 23. 2834 - 박스 정렬 step 1더보기$i$번째 박스를 $i$번 정점으로 생각하고 각 박스에 있는 숫자에 해당하는 정점으로 간선을 그립니다. 이렇게 하면 사이클이 생깁니다.step 2더보기크기가 1인 사이클은 이미 정리가 된 것이니 전부 없애줍니다. 만약 크기가 2 이상인 사이클의 개수가 0개면 이미 정리가 된 것이니 0을 출력합니다. 사이클이 1개면 1번만에 정리할 수 있습니다.각 정점을 이동하면서 정점이 가리키는 숫자를 출력하면 됩니다.step 3더보기사이클이 2개 이상이면 2번 만에 해결할 수 있습니다. 각 사이클에서 아무 점을 1개씩 고른 다음 섞어줍니다. 그럼 사이클이 하나로 합쳐집니다. 이제 사이클이 1개인 경우처럼 해결할 수 있습니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include.. 2024. 12. 16. 이전 1 2 3 4 ··· 11 다음
