와드의 블로그

문제스타크래프트 게임에서 뮤탈리스크 1마리가 SCV N대(최대 3대)를 공격하여 모두 파괴하려고 합니다. 뮤탈리스크는 한 번의 공격으로 3개의 타겟에 각각 9, 3, 1의 데미지를 입힐 수 있습니다. SCV들의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위한 최소 공격 횟수를 구하는 문제입니다.입력: 첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3), 둘째 줄에 각 SCV의 체력(1 이상 60 이하의 정수)이 주어집니다.출력: 모든 SCV를 파괴하기 위한 최소 공격 횟수를 출력합니다.링크: https://www.acmicpc.net/problem/12869풀이: 3차원 방문 배열을 이용한 탐색 최적화 (메모이제이션)SCV가 최대 3대이므로, 각 SCV의 남은 체력을 3차원 배열의 인덱스로 활용하여 탐색 ..

문제미로에서 지훈이가 불을 피해 탈출하려고 합니다. 미로의 가장자리에 도달하면 탈출에 성공한 것으로 간주합니다. 지훈이와 불은 매 분마다 상하좌우로 인접한 칸으로 이동(확산)하며, 불은 각 지점에서 네 방향으로 동시에 확산됩니다. 지훈이는 벽이 있는 칸이나 불이 번진 칸, 그리고 불이 번질 예정인 칸으로는 이동할 수 없습니다. 지훈이가 불을 피해 탈출할 수 있는 가장 빠른 시간을 구하는 문제입니다.입력: 첫째 줄에 행의 개수 R과 열의 개수 C가 주어집니다. 다음 R개의 줄에 미로의 상태가 주어집니다. (#: 벽, .: 지나갈 수 있는 공간, J: 지훈이의 초기 위치, F: 불이 난 공간)출력: 탈출할 수 있는 가장 빠른 시간을 출력합니다. 탈출할 수 없다면 "IMPOSSIBLE"을 출력합니다.링크: h..

문제N×N 크기의 땅이 있고, 각 땅에는 나라가 하나씩 존재하며 각 나라에는 인구수가 주어집니다. 인접한 두 나라의 인구 차이가 L명 이상, R명 이하라면 두 나라가 공유하는 국경선을 하루 동안 엽니다. 국경선이 열려 서로 이동할 수 있는 나라들을 '연합'이라고 하며, 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 됩니다. (소수점은 버림) 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.입력: 첫째 줄에 N, L, R이 주어지고, 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어집니다.출력: 인구 이동이 발생하는 일수(방문 횟수)를 출력합니다.링크: https://www.acmicpc.net/problem/16234풀이: DFS 탐색을 통한 연합 구성..