백준 27114 - 조교의 맹연습 (C++)

문제

• 문제 링크

  
   BOJ 27114 - 조교의 맹연습 
  

• 문제 요약

$3$가지 행동에 대한 에너지 소모량과 사용하고자 하는 에너지양이 주어진다.
정확히 사용하고자 하는 에너지양을 모두 소모하려할 때, 처음 바라보는 방향으로 돌아오는 행동 수행 횟수의 최솟값을 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ A, B, C, K ≤ 1,000,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

   결국 매 순간마다 표현되는 상태는 두가지다. 남은(소모해야 하는) 에너지양과 바라보고 있는 방향.
이에 따라 다음과 같은 정의를 내려보자.

$dp[i][j]$ : 남은 에너지양이 $i$이고 $j$의 방향을 바라보고 있을 때 제식 수행 횟수의 최솟값.

각 방향을 기준으로 $3$가지의 변화를 고려해주면 된다.

방향 $j$ 에서 $min($$A$를 수행할 때, $B$를 수행할 때, $C$를 수행할 때$)$ ... 점화식을 쓰기 전에 방향의 기준을 잡아놓고 생각 하는 것이 편할 것이다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int a, b, c, k, dp[1000001][4];
 
int f(int p, int q)
{
    if (p < 1) return q || p < 0 ? 1e9 : 0;
    int& t(dp[p][q]);
    if (!~t)
    {
        t = 1e9;
        t = min({ f(p - b, (q + 1) % 4), f(p - a, q - 1 < 0 ? 3 : q - 1), f(p - c, q + (q < 2 ? 2 : -2)) }) + 1;
    }
    return t;
}
int main()
{
    memset(dp, -1, sizeof dp);
    cin >> a >> b >> c >> k;
    cout << (f(k, 0) < 1e9 ? f(k, 0) : -1);
}

comment

풀이 후 기여 탭을 들어 갔는데 냅색 태그가 있어서 놀랐다.
생각해보니 냅색으로도 충분히 납득이 가는 문제였다.