이동식 저장소

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)$의 값을 배열에 저장..

Round #627 이후 2주만에 Div. 3 라운드가 열렸다. 그 사이에 Codeforces Global Round 7, Educational Codeforces Round 84 (Rated for Div. 2) 대회가 있었지만, 문제가 꽤 어려워 보여서 참가하지 않았다. 5일 동안 종만북으로 갈고닦은 실력을 보여주지! Dashboard - Codeforces Round #629 (Div. 3) - Codeforces codeforces.com A. Divisibility Problem $b - (a \bmod b)$를 출력하면 된다. 이때 나머지가 0이라면 0을 출력해야 한다. 설명 끝! 사실 이때까지만 해도 기세 좋았다. 다음 문제에서 아주 기초적인 실수를 하기 전까진.. B. K-th Beauti..

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

1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다. 이 나라의 주민들에게 성취감을 높여 주 www.acmicpc.net 그래프에서 독립 집합은 다음과 같이 정의된다. 그래프의 모든 정점 V의 부분집합 S에 대하여, 임의의 S의 두 정점 사이를 연결하는 간선이 없을 때 S를 독립 집합이라고 한다. 독립 집합의 크기는 정점..