devbelly

문제 www.acmicpc.net/problem/12003 알고리즘 Segment tree 풀이 두 개의 진열장에 다이아몬드를 진열하려 합니다. 같은 진열장 내에 있는 다이아몬드들은 그 크기의 차이가 $K$이하일 때만 진열이 가능합니다. 이러한 조건에서 진열할 수 있는 다이아몬드의 최대 갯수를 구하는 문제입니다. $N$제한이 5만이므로 $O(NlogN)$에 해당하는 알고리즘을 떠올려야합니다. 주어지는 다이아몬드의 크기를 정렬한 후 앞에서부터 크기의 차이가 $K$이하가 되도록 골라봅시다. $i$번째 다이아몬드부터 $i+j$번째 다이아몬드를 하나의 진열장에 넣었다면 $i+j+1$번째 다이아몬드부터 마지막 다이아몬드까지 어느 연속된 부분을 나머지 하나의 진열장에 넣어야합니다. 만약 각 다이아몬드를 선택했을 때..

문제 www.acmicpc.net/problem/20648 알고리즘 DP, 좌표압축 풀이 $N$개의 소들의 좌표가 주어질 때, 직사각형 울타리로 가둘 수 있는 소들의 집합의 수를 구하는 문제입니다. 두마리 이상의 소들을 울타리 안에 넣을 때가 문제가 됩니다. 만약 임의의 소 두마리를 고른 후 그 소들을 포함한 집합의 수를 셀 때, 답에 영향을 주는 소들의 위치는 다음 그림에서 노란색 부분과 같습니다. 화살표는 두 소의 위치를 나타낸 것입니다. 아래 노란색 사각형에서 소가 몇마리인지 세고 위에 노란색 사각형에서 소가 몇마리인지 센 후, 두 수를 곱하게 되면 선택한 두 소를 포함한 집합의 수를 구할 수 있습니다. 이 과정을 수행하기 위해 소들의 좌표를 압축한 후 $board$배열을 통해 원하는 사각형에 포함..

문제 www.acmicpc.net/problem/12012 알고리즘 Union Find, 오프라인 쿼리 풀이 헛간을 하나씩 닫아나갈 때 마다, 열린 헛간들의 연결성을 확인하는 문제입니다. 헛간을 닫을 때, 인접한 경로 또한 사라집니다. 우리가 아는 자료구조중 유니온 파인드는 조건에 따라 같은 노드들을 하나로 합치는 연산을 수행할 뿐, 합쳐진 노드들을 분리해내지는 않습니다. 연결성을 끊는 것은 쿼리를 거꾸로 보면 연결하는 것과 연관이 있습니다. 즉 쿼리를 순서대로 보지 않고 거꾸로 보며 유니온 파인드로 문제를 해결해 봅시다. 처음에 모든 헛간이 문을 닫은 상태에서 쿼리의 마지막부터 헛간을 다시 열어 나갑니다. 열려있는 헛간들의 연결성을 확인하는 것은 쿼리에 해당하는 헛간의 집합크기를 보면 됩니다. 마지막 ..

문제 www.acmicpc.net/problem/16964 알고리즘 DFS 풀이 그래프와 방문 순서가 주어질 때, 올바른지 확인하는 문제입니다. 그래프는 2차원 벡터로 표현이 가능합니다. 문제에서 입력을 받는 순서로 그래프를 만들어 방문하는 대신, 방문 순서를 기준으로 그래프를 정렬합니다. 이후 루트 노드에서 DFS를 수행하면 방문 순서가 빠른 노드부터 방문하게 되므로 해당 방문 순서가 올바른 순서인지 파악할 수 있습니다. 이를 위해 $rev$배열을 만들어 방문 순서가 빠른 노드로 그래프를 정렬하도록 했습니다. 코드 #include #define rep(i, n) for (int i = 0; i u >> v; --u, ..

문제 www.acmicpc.net/problem/11963 알고리즘 greedy 풀이 2$N$개의 카드를 나누어 가져 게임을 진행할 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $N$/2 이전 라운드는 큰 수를 내는 사람이 이기고, 이후 라운드는 작은 수를 내는 사람이 이깁니다. 큰 수 게임에서 bessie가 이길 수 있는 카드들이 있을 때, 최대한 작은 수를 내야 나중의 라운드를 준비할 때 유리합니다. 이를 위해 큰 수 게임을 진행할 때, elsie카드들 중 큰 수부터 처리해 나갑니다. 작은 수 게임도 마찬가지 이유로 elsie카드들 중 작은 수부터 처리해 나갑니다. 이 때 큰 수게임 중 카드를 낼 때, 이길 수 있는 카드들 중에서 작은 카드를 내게 되면 작은 수 게임에서 불리해질 수 도 있습니..

문제 www.acmicpc.net/problem/18874 알고리즘 segment tree 풀이 $j$보다 긴 머리카락들이 $j$가 될 때, badhair의 수를 구하는 문제입니다. 관찰이 조금 필요한 문제입니다. 우선 머리카락 길이가 변하는 것을 생각하지 않고 counting inversion을 할 때 브루트포스로 하면 $N^2$이 필요하고 문제에서 $N$제한은 10만이므로 $NlogN$에 inversion을 셀 수 있는 세그먼트 트리를 이용해야합니다. 쿼리($j$)마다 머리카락 길이를 업데이트를 하려면 아무리 빨리한다 하더라도 $O(N)$보다 빠를 순 없고 inversion을 세면 결국 시간초과입니다. 문제의 핵심은 $j$보다 긴 머리카락들이 $j$가 될 때, badhair을 발생시키는 머리카락들은 ..

문제 www.acmicpc.net/problem/3032 알고리즘 DP 풀이 선영이와 정인이가 게임을 합니다. 번갈아 숫자를 골라가며 고른 수의 인접한 수를 고를 때, 선영이가 이길 수 있는 경우를 세는 문제입니다. 인접한 수를 골라나가며 범위를 좁히는 것에서 DP를 떠올릴 수 있습니다. $solve(l,r,t)$= $l, r$부터 범위를 골라나갈 때, 선영이 차례에서 얻을 수 있는 최대 점수 ($t$가 짝수일 때 선영이 차례) 정인이의 차례($t$가 홀수일 때)에는 최악의 플레이를, 선영이의 차례에서는 최선의 플레이를 하면 선영이가 최대한 이길 수 있게 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..

문제 www.acmicpc.net/problem/14450 알고리즘 DP 풀이 소와 존이 가위바위보를 진행합니다. 소는 가위바위보 전문가라 존이 무엇을 낼지 미리 알고 있지만, 게을러서 연속적인 모션을 취합니다. 최대 $K$번 내기 시작하는 것을 바꿀 수 있을 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $i$번째의 결과가 바로 뒤의 $i+1$번의 결과에 영향을 미친다는 점에서 다이나믹 프로그래밍을 떠올릴 수 있습니다. 우리는 현재 가위바위보 단계에서 저장해야할 정보는 다음 세가지 입니다. 현재 몇 번째 가위바위보를 진행하고 있는지, $K$를 몇번 사용했는지, 현재 단계에서 소가 내고 있는 제스쳐는 무엇인지 입니다. 이를 위해 총 3차원의 배열을 사용하며 $cache[i][j][k]$가 영향을 미..