AtCoder Beginner Contest 265

A. Apple

문제 설명

하나의 사과를 X원에 사고, 3개의 사과를 Y원에 살 때 정확히 N개의 사과를 구매하기 위해 필요한 금액을 출력해야 한다.

알고리즘

A 치고는 생각할 부분이 있는 문제였다. 단순 그리디 풀이는 구현이 번거로울 것 같아서 dp 점화식으로 해결하였다.

n개의 사과를 사기 위해 필요한 금액을 \(dp[n]\)이라 할 때, \(dp[n] = min(dp[n - 1] + X, dp[n - 3] + Y\)로 계산할 수 있다.

B. Explore

문제 설명

총 N개의 방이 있고, i번에서 i+1번 방으로 이동하는 데 \(A_i\)초가 걸린다.

\(T\)초가 주어지고, 남은 시간이 0이 되는 일이 없도록 하여 1번에서 N번까지 갈 수 있는지 여부를 출력해야 한다.

이때, M개의 버섯이 있고 i번째 버섯은 \(X_i\)방에 있어 먹으면 \(Y_i\)만큼 시간이 늘어난다.

알고리즘

그리디하게 1번부터 N번까지 순서대로 이동하면 된다.

이동하면서 버섯이 있다면 모두 먹어주면 된다.

중간에 시간이 0이 되는 경우가 있으면 No, 아니면 Yes를 출력하면 된다.

C. Belt Conveyor

문제 설명

H x W 모양의 2차원 공간이 있고, 각 칸에는 U, D, L, R이 적혀져있다. 각 칸에 적힌 방향으로만 이동할 수 있다. 또한 공간 밖으로는 나갈 수 없다.

처음에 (1, 1)에 있고, 방향을 따라 계속하여 이동할 때 무한히 이동한다면 -1을, 언젠가는 멈춘다면 멈추게 되는 지점을 출력해야 한다.

알고리즘

간단하게 이동한 방향을 따라 이동하면서 방문 여부를 체크해주면 된다. 만약 이동할 수 없다면 현재 위치를 출력하고, 방문했던 칸을 이동하게 되면 -1을 출력하면 된다.

D. Iroha and Haiku (New ABC Edition)

문제 설명

크기가 N이고 정수로 이루어진 배열 A가 존재한다. 그리고 정수 P, Q, R이 주어진다.

이때, 아래 조건을 만족하는 x, y, z, w가 존재하는 지 여부를 출력해야 한다.

\(A[x:y) = P, A[y:z)=Q, A[z:w)=R\)

\(A[a:b)\)는 \(A[a]\)부터 \(A[b-1]\)까지 모두 더한 합을 의미한다.

알고리즘

투 포인터를 응용하여 해결하였다.

문제를 단순화하여 부분합이 P가 되도록 하는 x, y가 존재하는 지를 푸는 것은 투 포인터로 해결할 수 있다.

왼쪽 포인터와 오른쪽 포인터를 첫 번째 원소에 두고, 포인터 구간의 합이 P보다 작으면 오른쪽 포인터를 1 증가시켜서 구간합을 늘리고, 반대라면 왼쪽 포인터를 1 증가시켜 구간합을 줄이면 된다. 이를 반복하다가 구간합이 정확히 P가 되면 x, y가 존재하다는 뜻이다.

x, y, z, w인 경우에도 비슷하게 할 수 있다. 단, 오른쪽 포인터를 3개 준비하면 된다. 왼쪽 포인터를 l이라 하고, 오른쪽 포인터를 각각 p, q, r이라 하자. 위 과정을 똑같이 반복하면 된다. l부터 p까지 구간의 합과 P를 비교해서 포인터를 옮기고, l부터 q까지 구간의 합과 P+Q를 비교해서 포인터를 옮기며, l부터 r까지의 구간합과 P+Q+R을 비교해가며 포인터를 옮기면 된다.

모든 부분합이 일치하는 순간이 존재하면 Yes, 그렇지 않다면 No를 출력하면 된다.

E. Warp

문제 설명

(0, 0) 부터 총 \(N \le 300\)번 워프할 수 있다. 워프를 통해 (A, B)만큼 움직이거나 (C, D)만큼 움직이거나 (E, F)만큼 움직일 수 있다. N번 워프를 통해 이동한 경로의 경우의 수를 출력해야 한다.

중간에 \(M\)개의 장애물이 주어진다. 장애물의 좌표로는 이동할 수 없다.

알고리즘

총 3종류의 워프가 존재한다. 각 워프를 a, b, c번 이용하여 이동할 수 있는 경우의 수를 \(dp[a][b][c]\)라 하자. 그렇다면 dp식은 쉽게 세워진다.

\(dp[0][0][0] = 0, dp[a][b][c] = dp[a - 1][b][c] + dp[a][b - 1][c] + dp[a][b][c - 1]\)

a, b, c만 알고 있더라도 현재 위치를 계산할 수 있다. 만약 현재 위치에 장애물이 존재한다면, \(dp[a][b][c] = 0\)으로 처리해주면 문제를 해결할 수 있다.

F. Manhattan Cafe

문제 설명

N차원 상에서의 두 위치 p, q가 주어진다. 모든 좌표는 정수이다.

모든 좌표의 절댓값은 1000 이하이다.

p, q와 맨해튼 거리가 D 이하인 점 r의 개수를 출력해야 한다. D는 1000 이하인 음이 아닌 정수이다.

알고리즘

먼저 문제를 단순화하자.

p의 위치를 값이 모두 0인 점, 즉 원점으로 이동시키고, q의 위치를 q - p로 이동시켜도 두 점을 평행이동한 것이기 때문에 답은 달라지지 않는다. 또한, p가 원점으로 이동했으므로, q의 모든 좌표값에 절댓값을 씌워도 답은 달라지지 않는다.

좌표값이 작으므로 dp를 응용하면 해결할 수 있음을 짐작할 수 있다. 따라서 dp식을 세워보자.

먼저 \(dp[n][a][b]\)를 N개중 \(n\)개의 좌표값만 고려했을 때, 원점과는 거리가 \(a\)이고 q와는 거리가 \(b\)인 점의 개수라 정의하자. 그렇다면 \(n\)번째 점의 위치를 결정한 결과 거리가 \( (r, c) \)에서 \( (a, b) \)로 변한다고 할 때, 가능한 \(r, c\)를 모두 찾아야한다.

먼저 r[n] 값을 결정하면 현재 상태가 \( (a, b) \)일때 이전 상태인 \( (r, c) \)가 무엇이어야 하는지는 구할 수 있다. Naive하게 생각해보면 r[n]을 \(q[n] - D\)부터 \(D\)까지 모두 고려해야 하므로 최대 \(2D\)개의 점을 고려해야 한다. 이렇게 dp식을 도출하여 구한다면 \(O(ND^3)\)으로 시간초과가 나게 된다.

잘 관찰해보면, 탐색해야 할 점 \( (r, c) \)의 위치가 선형적이다. 먼저 r[n]이 k 이하인 경우에는 \( (r, c) = (a + k, b - q[n] + k) \)가 된다. r[n]이 k이상 q[i] 미만인 경우, \( (r, c) = (a - k, b - q[n] + k) \)가 된다. 마지막으로, k가 q[i] 이상인 경우, \( (r, c) = (a - k, b + q[n] - k) \)가 된다. 따라서 대각선의 누적합을 구해두고, 경곗값만 잘 처리해서 세 경우를 각각 \(O(1)\)에 구할 수 있다.

또한 dp식을 그냥 계산하면 공간복잡도에 문제가 생기지만, 대각선의 누적합을 저장해둔 후에는 다음 dp값을 계산할 때, 이전 dp값들이 모두 필요가 없으므로, 2차원 배열만으로 해결할 수 있다.

따라서 dp를 이용하여 시간복잡도 \(O(ND^2)\), 공간복잡도 \(O(D^2)\)으로 해결할 수 있다.