취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27114번 문제인 조교의 맹연습이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27114 

dp[E][k]를 에너지를 E만큼 소비했을 때의 처음 시작자세에서 90k도 회전한 상태로 서있기 위한 최소 구령횟수로 정의하자. 이 때, 에너지를 E만큼 소비하고 처음 시작자세에서 90k도 회전한 상태가 되기 위해서는 마지막으로 "좌로 돌아", "우로 돌아" 또는 "뒤로 돌아" 셋 중 하나의 제식 수행을 하였을 것이므로, 이와 같은 관계를 이용해 dp에 관한 점화식을 세울 수 있음을 관찰할 수 있다.

위의 관찰로 얻을 수 있는 점화식과 메모이제이션을 이용해 문제를 해결해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int A, B, C, K;
int dp[2000001][4];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0][0] = 1;

	cin >> A >> B >> C >> K;
	for (int k = 0; k < K; k++) {
		for (int d = 0; d < 4; d++) {
			if (dp[k][d]) {
				if (dp[k + A][(d + 3) % 4]) dp[k + A][(d + 3) % 4] = min(dp[k + A][(d + 3) % 4], dp[k][d] + 1);
				else dp[k + A][(d + 3) % 4] = dp[k][d] + 1;
				if (dp[k + B][(d + 1) % 4]) dp[k + B][(d + 1) % 4] = min(dp[k + B][(d + 1) % 4], dp[k][d] + 1);
				else dp[k + B][(d + 1) % 4] = dp[k][d] + 1;
				if (dp[k + C][(d + 2) % 4]) dp[k + C][(d + 2) % 4] = min(dp[k + C][(d + 2) % 4], dp[k][d] + 1);
				else dp[k + C][(d + 2) % 4] = dp[k][d] + 1;
			}
		}
	}

	cout << dp[K][0] - 1;
}