devbelly

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

문제 www.acmicpc.net/problem/14169 알고리즘 BFS 풀이 레이저를 시작점에서 농장까지 비추도록 거울을 설치해야 합니다. 이때 필요한 최소의 거울 수를 묻고 있습니다. 좌표가 작다면 이 문제처럼 2차원 배열을 만든 후 BFS를 수행하면 됩니다. 하지만 이 문제는 좌표의 범위가 10억 이하이므로 배열을 선언할 수 없을 뿐더러 거울을 설치할 수 있는 장소의 개수인 $N$이 최대 10만이므로 좌표압축을 해도 2차원 배열안에는 넣을 수 없습니다. 핵심은 주어진 좌표를 BFS를 사용할 수 있도록 적절하게 자료구조에 넣는 것 입니다. 이를 위해 $adj$를 사용했습니다. 인접한 좌표끼리 연결할 때(인접하는 것은 x좌표가 동일한 좌표끼리 묶고 y좌표가 동일한 좌표끼리 묶는 것 입니다), 바로 근..

문제 www.acmicpc.net/problem/19606 알고리즘 BFS 풀이 격자판마다 양수가 쓰여있습니다. 양수를 V라고 가정할 때, r X c = V 에 해당하는 (r, c)로 이동이 가능합니다. (1, 1)에서 시작하여 (M, N)으로 이동 가능한지 판별하는 문제입니다. (1,1)에서 BFS를 수행하려면 조금 까다롭습니다. 가능한 (r, c)를 조사를 해야하는데 이 과정이 시간이 걸립니다. 역으로 (M, N)에서 (1,1)로 이동하면 비교적 간단해집니다. V값을 담고 있는 좌표들을 조사하는 방법으로 수행하면 되기 때문입니다. V마다 좌표를 담기 위해 2차원 배열을 사용했고 BFS를 수행해 나가면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n..

문제 www.acmicpc.net/problem/2487 알고리즘 union find 풀이 섞기 수열이 주어질 때, 원래의 카드 순서로 돌아오기 위한 궤적을 구하는 문제입니다. 카드들이 턴마다 어디로 움직이는지 파악해야합니다. 카드들이 섞기 수열에 따라 움직이며 각 카드마다 제자리로 돌아와야합니다. 같은 사이클을 사용하는 카드들의 크기들을 파악한 후 사이클의 최소 공배수를 구하면 궤적이 나오게 됩니다. 아래 유니온 파인드에서 $p$는 자신의 부모를 나타내며, 만약 $p$값이 음수라면 그 인덱스가 부모임을 나타내며 절댓값은 해당 사이클의 크기를 나타내도록 구현했습니다. 코드 #include #include #define rep(i, n) for (int i = 0; i < n; ++i) #define RE..

문제 www.acmicpc.net/problem/14168 알고리즘 DP 풀이 H종류의 소와 G종류의 소가 주어집니다. 순차적으로 (연속될 필요는 없음) 방문했을 때 최소의 에너지 구하기. 시작은 H종류의 1번소에서 시작해 H종류의 h번소에서 끝나야합니다. 경찰차와 비슷한 문제입니다. $cache$를 다음과 같이 선언합시다. $cache[i][j][k]$ = H종류의 $i$번째 소, G종류의 $j$번째 소까지 방문이 끝났을 때, 필요한 에너지 최솟값. $k$는 $i, j$ 소중에서 현재 위치의 소를 알기 위함입니다. $k$값이 0이면 H종류의 소에 있음을 나타내고 $k$값이 1이면 G종류의 소에 위치함을 나타냅니다. $cache[i][j][k]$가 갱신할수 있는 상태는 $cache[i+1][j][k]$와..

문제 www.acmicpc.net/problem/8875 알고리즘 Greedy 풀이 무게와 크기가 있는 장난감 $T$개가 주어집니다. 장난감을 정리하기 위해 연약한 로봇 $A$개와 작은 로봇 $B$개가 주어질 때, 정리하기 위한 최소 시간을 구하는 문제입니다. 연약한 로봇은 장난감의 크기와는 상관없이 자기보다 무게가 덜 나가는 장난감을 정리할 수 있고 작은 로봇은 무게에 상관없이 자기보다 작은 장난감을 정리할 수 있습니다. 이분탐색을 통해 정답을 찾아 나가야 합니다. 효율적인 정리를 위해 연약한 로봇은 각자가 처리할 수 있는 장난감들이 있다면 그 중에서도 가장 크기가 큰 장난감들부터 정리해나가면 됩니다. 연약한 로봇의 처리가 끝난 후 작은 로봇들은 정리가 되지 않은 장난감들을 처리해나가는데, 크기가 가장..

문제 www.acmicpc.net/problem/1126 알고리즘 DP 풀이 $N$개의 블록이 주어집니다. 취사선택하여 두 개의 탑을 높이가 같도록 쌓을 때, 최대 높이를 구하는 문제입니다. DP 배열의 의미를 잘 생각해야 하는 문제입니다. 블록을 사용할 때마다 변하는 것은 높이입니다. 두 개의 탑의 상태를 알면 정답을 알 수 있으므로 다음과 같이 생각할 수 있습니다. $cache[i][j]$= $i$번째 블록까지 사용했고 양 탑의 높이차가 $j$일 때 가장 높은 탑의 높이 현재 상태에서 $h[i]$ 블록을 가지고 할 수 있는 행동은 세 가지가 있습니다. 첫 번째는 사용하지 않기, 두 번째는 높이차를 더 크게 하기, 세 번째는 높이차를 작게 하는 것입니다. 앞의 두 가지 행동은 헷갈릴만한 것이 없지만 세..

문제 www.acmicpc.net/problem/15587 알고리즘 BFS 풀이 Bessie가 트리 형태의 목장에서 탈출하려 합니다. 이때 이 탈출을 제지해야하는 최소의 농부 수를 구하는 문제입니다. 탈출구는 리프노드입니다. 만일 한 농부가 $u$노드까지의 거리가 베시보다 가까우면서 다른 농부들보다도 가깝다면 다른 농부들을 카운트할 필요는 없습니다. 이를 위해 다양한 source로부터(여기서는 리프노드, 농부들의 시작점) bfs를 수행할 것입니다. $dist$의 상태에는 3가지가 있습니다. 아직 방문하지 않은 상태인 -1, 농부가 방문한 상태인 0, bessie가 도착한 int_max의 상태입니다. 아래 코드에서 가장 눈여겨 볼 점은 bessie에 해당하는 노드를 queue에 넣을 때, 농부들보다 뒤에 ..