(06/20 ~ 06/26) 랜덤 골드 디펜스

BOJ 10767 Palindromic Paths

N by N 크기의 격자판의 각 칸에 알파벳이 쓰여있고, (0, 0)에서 부터 (N-1, N-1)까지 오른쪽 또는 아래 칸으로만 이동하여 가는 모든 경로에 대해, 지나온 알파벳을 순서대로 놓은 문자열들 중 서로 다른 팰린드롬의 개수를 구하는 문제.

$2 \leq N 18$ 이라는 조건이 있어서, 브루트포스로 해결되겠구나 하는 느낌을 받았다. 그러나 모든 경로를 보려면 총 $2^35$ 만큼의 경로를 봐야하므로, 시간내에 해결할 수 없다.

팰린드롬의 길이는 항상 $2N-1$로 나오므로, 시작점에서 출발하여 길이 N의 prefix, 끝점에서 출발하여 길이 N의 surfix를 만들고, 두 prefix와 surfix가 같은 경우를 세어주면 된다.

MITM이랑 해시셋 연습하기에 나쁘지 않은 문제같기도?

BOJ 10037 Decorating the Pastures

이분그래프인지 판별하고, 이분그래프라면, 그래프의 두 그룹중 한 그룹의 크기를 최대한 크게 만들어야한다.

이분그래프라면 정점을 두 그룹으로 나누는 방법은 유일하므로, 이분 그래프 판별을 수행하면서, 각각의 정점을 두 그룹으로 나누고, 더 큰 그룹의 크기를 답에 더해주면 된다.

입력으로 들어온 그래프가 연결그래프가 아닐 수 있음에 주의하여 문제를 해결하였다.

BOJ 17025 Ice Perimeter

격자상에서 Connected Component들의 크기와 둘레를 구하면 되는 문제.

크기를 구하는 것은 간단하게 해결할 수 있고, 둘레는 '#'인 격자에서 상하좌우의 칸 중 '.'이거나, 아예 격자판 밖으로 벗어나는 것들의 개수를 세어 모두 더해주면 된다.

BOJ 2923 숫자 게임

이번주에 해결한 가장 재미있었던 문제중 하나다.

배열 A, B가 주어질때, 각각의 i에 대해서 A[:i]와 B[:i]의 각 원소를 잘 짝짓는다. 이때 짝지어진 두 원소의 합 중 최대값을 최소화하는 문제.

그냥 특정 배열 A, B가 주어져있다면 A는 오름차순으로, B는 내림차순으로 정렬하여 짝짓는 것이 최적이 된다. 그러나 이 문제의 어려운 점은 배열에 수가 하나씩 추가될때마다의 답을 구해야하는 것 이다. 힌트는 각 배열의 수의 범위가 100 이하임에 있다.

수열 A, B 각각에 대해서 어떤 수 i가 몇번 등장하는지 세어주는 배열을 만들어두고, A배열은 1부터, B배열은 100부터 시작하여 한번에 짝지어줄 수 있는 수를 있는대로 많이 짝지어주고, 그중 합의 최대값을 찾으면 된다.

BOJ 9880 Recording the Moolympics

회의실 배정의 회의실 2개짜리 버전.

두 회의실 각각에 최적으로 선택한 회의의 집합 P, Q가 있다고 하고, 아직 선택되지 않은 집합 R이 있다고 하면, 회의실 배정에서 풀었던 전략에 따라 가장 빨리 끝나는 회의를 골라서 집합에 추가하는 것이 이득일 것 같다.

문제는 P에도 Q에도 동시에 넣을 수 있으면 어느쪽에 넣는 것이 최적인지 모른다는 것이었고, 이를 DP로 해결했다.

회의들을 빨리 끝나는 순으로 정렬하고 시작하자.

dp 테이블을 다음과 같이 정의하면 문제가 간단하게 해결된다.

D(i, j, k) = i번째 회의까지 회의실에 배정을 마쳤으며, 첫번째 회의실의 가장 마지막에 끝나는 회의의 번호가 j, 두번째 회의실은 k일때, 최대한 많이 배정했을때 배정된 회의의 수.

어느 상태 (i, j, k)에 i+1번째 회의가 어떻게 추가되어 상태가 어떻게 전이될지를 생각하면 된다.

BOJ 6129 Obstacle Course

BOJ 6087 레이저 통신과 똑같은 문제.

bfs를 수행해주는데, 단순히 상하좌우에 있는 좌표만 추가하는 것이 아니라, 상하좌우 직선상에 어떤 벽으로도 가로막혀있지 않은 좌표들을 모두 큐에 넣어주어 bfs를 수행하면 된다.