BOJ 27114 - 조교의 맹연습

문제 링크

문제#

공군 훈련소의 훈육조교는 훌륭한 조교가 되기 위해 오늘도 피나는 제식 연습을 진행한다. 오늘 연습하려고 하는 제식은 총 세 가지로, 현재 바라보는 방향을 기준으로 각각 왼쪽으로 $90^\circ$ 회전하는 좌로 돌아, 오른쪽으로 $90^\circ$ 회전하는 우로 돌아, 뒤로 $180^\circ$ 회전하는 뒤로 돌아이다.

좌로 돌아, 우로 돌아, 뒤로 돌아를 $1$회 수행하는 데에는 각각 $A, B, C$만큼의 에너지가 든다. 오늘 조교의 총 에너지는 $K$만큼 남아있으며, 최고의 훈련을 위해 모든 $K$만큼의 에너지를 전부 소진하려고 한다.

조교는 본인의 에너지를 모두 소모하여 연습을 끝냈을 때 처음 바라보던 방향과 완벽히 동일한 방향을 바라보고자 한다. 또한, 어지러움으로 인한 흐트러짐을 막기 위해 제식의 수행 횟수를 최소화하고자 한다.

조교가 정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 바라보며 연습을 끝내고자 할 때 제식 수행 횟수의 최솟값을 구하여라.

입력#

첫 번째 줄에 각각 좌로 돌아, 우로 돌아, 뒤로 돌아에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B,C,K\leq 1\,000\,000)$

출력#

정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 바라보며 연습을 끝내고자 할 때 제식 수행 횟수의 최솟값을 출력한다.

만약 정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 보는 것이 불가능하다면, $-1$을 출력한다.

풀이#

단순히 에너지 합만 맞추면 되는 게 아니라, 마지막 방향까지 원래 위치로 돌아와야 한다. 그래서 상태를 dp[사용한 에너지][현재 방향]으로 두는 DP가 필요하다.

초기 상태는 dp[0][0] = 0이고, 각 상태에서 세 가지 회전을 시도하며 다음 에너지와 다음 방향을 갱신한다. 같은 에너지와 방향에 도달하는 더 짧은 방법이 있으면 그 값으로 갱신하면 된다.

회전마다 방향 변화량이 서로 다르기 때문에, 단순히 에너지만 맞춘다고 끝나지 않는다. 예를 들어 총 에너지가 같아도 어느 회전을 몇 번 썼는지에 따라 최종 방향이 달라질 수 있으므로, 방향 차원을 함께 들고 가야 한다.

코드에서도 현재 방향을 0~3으로 두고, 세 가지 회전에 대해 (현재 방향 + 회전량) % 4로 다음 방향을 만든다. 그렇게 해서 정확히 에너지 K를 썼을 때 방향이 다시 0인 상태 중 최소 동작 횟수를 답으로 사용한다. 마지막에 dp[K][0]이 갱신되지 않았다면 불가능하므로 -1이다.

코드#

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int K, INF = 1000001;
int energy[4];
int dp[1000001][4];
 
void solve(int K) {
	for (int i = 0; i <= K; i++) {
		for (int j = 0; j < 4; j++) {
			if (dp[i][j] == INF) continue;
 
			for (int k = 1; k <= 3; k++) {
				int nextDir = (j + k) % 4;
				int nextEnergy = i + energy[k];
 
				if (nextEnergy <= K) {
					dp[nextEnergy][nextDir] = min(dp[nextEnergy][nextDir], dp[i][j] + 1);
				}
			}
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int K = 0;
	// 우 -> 뒤 -> 좌
	cin >> energy[3] >> energy[1] >> energy[2] >> K;
 
	for (int i = 0; i <= K; i++) 
		for (int j = 0; j < 4; j++) dp[i][j] = INF;
		
	dp[0][0] = 0;
	solve(K);
 
	if (dp[K][0] == INF) cout << -1 << '\n';
	else cout << dp[K][0] << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: $O(K)$
• 공간 복잡도: $O(K)$

마무리#

에너지 총합만 맞추는 배낭처럼 보이지만, 방향 상태 하나가 더 들어간다. 이 방향 차원까지 함께 관리해야 정답이 된다.