이동식 저장소

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

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

2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다. www.acmicpc.net 트리를 격자판에 그리려 한다. 격자판의 한 칸에는 노드 하나가 들어가며, 주어진 조건에 따라 그려야 한다. 가장 결정적인 조건은 3번 조건이다. 3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. ..

본문에서 약간의 새벽감성이 느껴진다. ㅋㅋ 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 미로를 돌아다니며 열쇠를 얻어서 출구로 나가야 하는 문제이다. 당연히 이런 류의 문제는 BFS를 적용하면 된다. 그런데 조금 불편한 조건이 하나 있다. 미로에는 문이 있을 수 있는데, 대응하는 열쇠가 있어야 문을 지나갈 수 있다. 벽뿐만 ..