PS - 알고리즘 (48) 썸네일형 리스트형 24231 - 해석 step 1더보기dp[i][j] : i번째 부터 j번째 까지만 있다고 했을 때 만들 수 있는 올바른 괄호 문자열의 개수step 2더보기dp[i][j]를 채운다고 생각해 봅시다. i번째 문자는 반드시 여는 괄호여야 합니다. 이 문자는 i+1, i+3. i+5,... 번째 문자와 짝을 이룰 수 있습니다(물론 그 문자는 닫는 괄호여야 합니다). 만약 k번째 문자와 짝을 이루었다면 dp[i][j] += dp[i+1][k-1] * dp[k+1][j]를 해줍니다.이런 식으로 dp를 채워나가면 됩니다. 탐색 순서는 j-i가 작은 순서대로 탐색하면 됩니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include#include#include.. 23752 - 카드 잘 섞기 step 1더보기2번 쿼리는 그냥 하면 됩니다.1번 쿼리에서 카드 장수가 홀수인 경우만 생각해 봅시다. 카드 5장이 다음과 같이 있습니다. 카드의 위치는 위에서 부터, 0-base로 셉니다.카드의 인덱스를 2배 한 다음 절반씩 나누고 잘 끼워 넣습니다.그럼 카드의 장수를 $N$이라 할 때 각 카드의 처음 인덱스를 $a_i$라 할 때 셔플 후의 인덱스는 $(a_i*2)\%N$이 됩니다. 이 동작을 $z$번 반복하면 $a_i*2^z\%N$이 됩니다.step 2더보기카드의 장수가 짝수인 경우입니다. 제일 아래쪽 카드의 위치는 절대 바뀌지 않습니다.마지막 카드만 빼고 살펴봅시다. 5장일 때와 다르지 않습니다.즉 $1\,x\,y\,z((y-x)\%2==1)$ 쿼리는 $1\,x\,y-1\,z$과 완벽히 같습니다.코.. 27086 - 점수 내기 step 1더보기수학토끼가 내야 하는 금액은 $O(N)$에 구할 수 있으니 신경쓰지 맙시다.$y=1$로 계산하고 마지막에 진짜 y를 곱해줍니다.$(x, \lceil 2*10^5 / x \rceil)$ 크기의 배열을 생각해 봅시다. 점수가 $X_i$인 학생은 $(X_i\%x, \lfloor X_i/x\rfloor)$ 칸에 들어가 있습니다. 아래는 각 점수별로 어떤 칸에 들어가는지 표시해 두었습니다. 각 열마다 해당 열에 있는 사람들의 몫의 합과 그 열에 있는 사람의 수를 저장해 둡니다. 아래 그림에서 칸에 있는 숫자는 해당 칸에 해당하는 사람의 수입니다.step 2더보기점수가 가장 낮은 사람을 봅시다. 이 사람은 모든 사람(같은 칸에 있는 사람 제외)과 비교를 해야 합니다. 어떤 칸에 사람이 있는지에 따라.. 15807 - *빛*영*우* step 1더보기 https://www.acmicpc.net/problem/5419 step 2더보기그림을 반시계 방향으로 45도 돌린다고 생각해 봅시다. 그럼 위 문제를 푸는 것과 같습니다.새로운 좌표축 2개를 도입합니다. 하나는 $y=x$고 다른 하나는 $y=-x$입니다. 새로운 좌표 축에 맞춰 좌표를 재설정하고 위 문제를 해결합니다.축을 바꾸는 것을 해봅시다. 위 그림에서 점 $A$는 원래 축 기준 (1,3)에 있습니다. 그리고 새로운 축(빨간색) 기준으로는 (-2, 4)에 있습니다. 원래 축 기준 $x$좌표를 $X$, 원래 축 기준 $y$좌표를 $Y$라고 하면바뀐 축 기준 $x$좌표 : $X-Y$바뀐 축 기준 $y$좌표 : $X+Y$로 쉽게 계산할 수 있습니다. step 3더보기이제부터 모든 좌표.. 9642 - Omar’s Bug 문제 번역더보기Omar는 다음 이분탐색 코드를 만들었습니다.int findFirstGreaterThanOrEqual(int array[], int N, int X) { int start = 0, end = N; while (start X) { end = middle; } else { start = middle + 1; } } return start;} 파라미터는 다음 조건을 만족합니다.$array$는 1개 이상 99개 이하의 수가 들어있습니다.$array$의 모든 숫자는 서로 다르고 오름차순입니다.$array$에 있는 수는 최대 100입니다.$N$은 $array$의 크기입니다.$X$는 최대 100입니다.만약 $X$보다.. 17242 - Kaka & Bebe step 1더보기$dp[i][j]$ = i번째 정점에 있고 지금까지 Kaka를 j마리를 봤을 때 그때까지 볼 수 있는 Bebe의 최소 마리 수를 구합니다.step 2더보기위 dp를 구해봅시다. 모든 간선마다 Kaka와 Bebe가 한 마리씩은 있기 때문에 $dp[i][j]$는 $dp[k][l](l>j)$에만 영향을 미칠 수 있습니다. 즉, $j$가 작은 $dp$부터 출발해서 순서대로 채워주면 됩니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#include#includeusing namespace std;vector>> v[2000];priority_queue> q;int dp[2000][2000],ch[2000][2000];int main() { int n, m,.. 17398 - 통신망 분할 step 1더보기원래 상태에서 연결을 끊는다고 생각하지 말고 이미 연결을 다 끊어놓은 상태에서 거꾸로 연결을 한다고 생각합니다.step 2더보기$Q$번의 연결을 다 끊어놓은 상태를 구할 수 있습니다. 유니온 파인드를 이용해서 어떤 정점들이 이어져 있는지 확인합니다. 그 상태에서 쿼리를 반대로 봅니다. 두 정점이 같은 집합에 있다면 해당 쿼리를 실행했을 때 통신망이 나뉘어지지 않았다는 뜻입니다. 두 정점이 다른 집합에 있다면 각 집합의 크기를 곱한 값만큼 비용이 발생했다는 뜻입니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#includestruct data { long long int x, y;}b[200000];long long int tr[200000];long long i.. 13209 - 검역소 step 1더보기더보기검역소를 설치하는 것은 트리에서 간선을 끊는 것으로 생각할 수 있습니다. 즉 $K$개의 간선을 끊었을 때 각 트리에 있는 사람들 수의 합의 최대값을 최소로 하는 문제입니다. 문제를 살짝 바꿔서 "각 트리에 최대 $X$명의 사람이 있을 수 있다고 하면 적어도 몇 개의 다리를 끊어야 하는가"로 생각해 봅시다. $X$가 커질수록 끊어야 하는 다리의 수는 적어집니다. 따라서 이분 탐색으로 $X$값을 찾을 수 있습니다.step 2더보기더보기bridge[i] = i번째 정점을 루트로 생각했을 때 끊어야 하는 다리의 최소값person[i] = bridge[i]를 최소로 만들었을 때 i번째 정점이 속한 트리에 있는 사람 수. 이 두 dp를 채운다고 생각합니다. 어떤 정점이 시작점이여도 답은 바뀌지.. 3043 - 장난감 탱크 step 1더보기더보기행과 열을 분리해서 볼 수 있습니다.step 2더보기더보기$N$ * $N$ 크기에 $N$개의 탱크를 놓습니다. 어떤 행이나 열에도 2개 이상의 탱크가 놓일 수 없으니 결국 모든 행에 1대, 모든 열에 1대의 탱크가 놓입니다.열을 먼저 생각해 봅시다. 처음에 탱크가 배치되어 있고 이 탱크들을 모든 열에 1대씩 있도록 재배치해야 합니다.처음 배치에서 두 탱크를 고른다고 생각해 봅시다. 왼쪽에 있는 탱크를 $X$, 오른쪽에 있는 탱크를 $Y$라고 합시다. 이 두 탱크는 재배치된 이후에도 $X$가 $Y$ 왼쪽에 있어야 합니다. 이것을 잘 생각해 보면 열을 기준으로 정렬한 뒤 제일 왼쪽에 있는 탱크는 1번째 열, 두번째로 왼쪽에 있는 탱크는 2번째 열, ..., $N$번째로 왼쪽에 있는 탱크.. 11873 - 최대 직사각형 step 1더보기https://www.acmicpc.net/problem/6549https://codestudycafe.tistory.com/37step 2더보기"직사각형의 밑변이 i번째 행에 있다면 만들 수 있는 직사각형의 최대 넓이는 얼마일까" 라는 질문을 모든 행에 대해서 하면 됩니다.i가 정해졌다고 할 때, 0 위에 있는 1들은 아무 의미 없습니다. 그곳에 직사각형이 도달할 수 없기 때문이죠. 아래는 예제의 첫번째 케이스에서 i=3일 때입니다.그렇다면 이 문제는 "히스토그램에서 가장 넓은 직사각형이 무엇인가"를 푸는 문제로 바뀝니다.이 문제를 푸는데 N, 이 문제의 개수가 N이므로 N^2에 해결할 수 있습니다.코드더보기#include#includeusing namespace std;stack> s.. 이전 1 2 3 4 5 다음
