이동식 저장소

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)을 활용해야 한다. 관찰 로봇은 위쪽으로 움직일 수 없다. 따라서 지형의 마지막 행에 도착한 로봇은 반드시 오른쪽으로만 이동해야 한다...

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)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. ..

5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 대회에서 사용된 공식 테스트 케이스가 제공된다. 압축을 풀고 C번 데이터를 찾으면 된다. 루빅스 큐브를 주어진 방법대로 돌린 후의 윗면을 출력하는 문제이다. 어려울 건 하나도 없다. 큐브의 각 면을 저장한 ..