문제 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 풀이 적어도 유치해야 하는 고객 수 C명과 도시의 개수 N이 주어진다. 이때 각 도시에는 홍보비용과 그 비용으로 유치할 수 있는 고객에 대한 정보가 제공된다. 이때, 최소 비용으로 적어도 C명의 고객의 수를 유치하는 경우를 반환하는 문제이다. 문제를 풀기 위해서는 메모이제이션을 통해, 다음과 같이 점화식을 세우면 해결할 수 있다. `dp[N명의 고객을 유치하는데 드는 비용] = min(dp[N명의 고객을 유치하는데 드는 비용], dp[N명의 고객을..
문제 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 풀이 입력값으로 파이어볼의 위치 (r, c), 질량(m), 방향(d), 속력(s)이 주어진다. 시뮬레이션 문제이므로 다음과 같은 과정을 순차적으로 진행한다. 모든 파이어볼은 자신의 방향으로 속력만큼 이동한다. 이동을 마친 후, 이동된 파이어볼들이 같은 칸에 2개 이상 있다면 다음과 같이 처리한다. 파이어볼은 4개로 나누어진다. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다. 질량은 `합쳐진 파이어볼 질량의 ..
문제 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제 풀이 문제에서 격자판과 궁수의 공격 거리 제한 D가 주어 질 때 제거할 수 있는 적의 최대 수를 출력하는 문제이다. 궁수는 3명을 배치할 수 있으며, 배치 가능한 범위는 열의 범위인 M까지 이다. 궁수의 경우 3명만 배치 가능하므로 각 좌표에 대해 조합(Combination)으로 경우의 수를 구해 후보군을 구한다. 후보군을 구하였다면 후보군을 모두 순회하면서 공격 가능한 거리에 따라 적을 제거하고 적이 앞으로 움직이는 과정을 반복하여 제거한 적의 수를 비교하여 최..
문제 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 문제 풀이 목표가 되는 문자열과 일치하는 경우의 수를 찾는 문제이다. 이를 위해서 `상, 하, 좌, 우`로 K 만큼씩 이동할 수 있다. 문제를 풀기 위해서는 단순히 DFS를 통해 경우의 수를 찾게 되면 시간 초과가 발생한다. 따라서 메모이제이션을 통해 이미 체크한 경우의 수라면 해당 경우의 수를 체크하지 않아야(가지치기) 한다. 처음에는 `dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))`를 사..
