이동식 저장소

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 숫자의 배치 순서를 바꿔서 수를 최대로 만들어야 하는 문제이다. 무식하게 풀어보기 모든 가능한 $(i, j)$ 쌍을 바꿔 보는 방법을 생각해 볼 수 있다, 그러나 경우의 수가 최대 $\left(\begin{array}{c}7\\ 2\end{array}\right)^{10}=16,679,880,978,201$개나 있으므로 완전 탐색으로는 문제를 풀 수 없다. 그렇다면 기억해 보자 메모이제이션을 활용하여 중복 계산을 줄여 보자. 다음을 정의한다. $ans(n, dep) = dep$번 교환하여 얻은 수가 $n$일 때, 교환을 완료하여 얻..

이 문제의 대회 데이터가 공개되어 있으니 사용해 보자. 원문 제목은 labudovi이다. 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 얼음을 녹이면서 백조가 만날 수 있는지 확인해야 한다. 물과 인접한 얼음이 녹는다는 설명에서 BFS를 적용해야..

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 게임판을 탐색하는 전형적인 동적 계획법 문제이다. 어떤 칸에서 시작하여 게임을 진행할 수 있는 최대 횟수는 정해져 있으며, 그러한 횟수가 변하지 않기 때문에 한번 계산한 결과를 계속해서 써먹을 수 있고, 그래야만 한다. 메모이제이션 없는 완전 탐색의 시간복잡도는 $O(4^{nm})$이다. 실제로는 구멍에 빠지는 등의 종료로 인해 더 작겠지만 전체적으로 보면 지수 꼴의 시간 복잡도를 갖는다. 단 여기서 사이..

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문자열을 팰린드롬인 부분 문자열로 나눠야 한다. $solve(i)$를 $[i, len]$ 구간의 정답으로 정의하자. 이 값은 $[i, len]$이 팰린드롬이라면 1, 그렇지 않다면 $min_{j=i}^{len} (1 + solve(j))$이다. 물론 $[i, j]$ 부분 문자열은 팰린드롬이어야 한다. 단, 중복 계산을 방지하기 위해 $solve(i)$의 값을 배열에 저장..

코로나19의 빠른 종식을 기원합니다. 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 지형을 탐사하며, 탐사 가치를 최대로 해야 하는 문제이다. 이때 로봇은 오른쪽, 왼쪽, 아래로만 움직일 수 있으며, 한 번 방문한 지역은 다시 방문할 수 없다. 전형적인 완전 탐색 문제이다. 그러나 완전 탐색으로는 최대 O(3^(N+M))을 감당할 수 없으므로 동적 계획법(이하 dp)을 활용해야 한다. 관찰 로봇은 위쪽으로 움직일 수 없다. 따라서 지형의 마지막 행에 도착한 로봇은 반드시 오른쪽으로만 이동해야 한다...