백준 27114 조교의 맹연습

문제

수행 횟수를 최소화하면서도 마지막에는 동일한 방향을 바라보면서 끝날 수 있도록 제식수행을 한 횟수를 구하면 된다. 처음에는 그리디로 풀어야 하나 싶었지만, 그리디로 했을 때 다른 제식 행동으로 했을 때 성공할 수 있는 제식 또한 성공하지 못하는 방식으로 흘러갈 수 있게 되기 때문에 아니 아닐 것 같다. 그리디로 유명한 잔돈 거슬러주기 문제에서는 해당 조합으로 상위 가치의 돈을 만들어 낼 수 있다는 조건이 걸려있기 때문에 해당 조건이 없다면 그리디로 풀기 어려워진다.

그렇다면 수행 횟수를 최소로 하는 방법은 아무래도 dp를 이용하여 각 횟수마다 최소가 될 수 있는 경우를 구하는 것이 최고라고 생각한다. 그렇다면 점화식이 어떻게 나올까? dp 배열에서 가질 수 있는 최소의 제식 수행 횟수를 기록하고, 제식에는 세 가지 경우가 있으니까 세 가지 경우 중 이제까지 제일 최소로 나온 경우만 구하면 된다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, b, c, k] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split(" ")
  .map(Number);
 
 
const dpArr = new Array(k + 1).fill(Infinity);
dpArr[0] = 0;
 
for (let i = 0; i <= k; i++) {
  if (dpArr[i] !== Infinity) {
    for (let action of actions) {
      if (i + action <= k) {
        dpArr[i + action] = Math.min(dpArr[i + action], dpArr[i] + 1);
      }
    }
  }
}
 
console.log(dpArr[k] === Infinity ? -1 : dpArr[k]);
 

처음에는 이렇게 해보고자 했지만 왜인지 틀렸다고 계속 나왔다 생각해보니 회전하는 경우를 고려하지 않고 풀었기 때문이었다. 근데 또 막상 방향까지 추가해서 만들려니 정말 어떻게 할지 잘 모르겠다… 결국 블로그를 찾아보았다

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [A, B, C, K] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split(" ")
  .map(Number);
 
const cost = [A, B, C];
const dir = [3, 1, 2];
const dp = new Array(K + 1);
 
for (let i = 0; i <= K; i++) {
  dp[i] = new Array(4).fill(Infinity);
}
dp[0][0] = 0;
 
for (let i = 0; i <= K; i++) {
  for (let j = 0; j < 4; j++) {
    if (dp[i][j] === Infinity) continue;
 
    for (let c = 0; c < 3; c++) {
      const nextEnergy = i + cost[c];
      if (nextEnergy > K) continue;
 
      const nextDirection = (j + dir[c]) % 4;
      dp[nextEnergy][nextDirection] = Math.min(
        dp[nextEnergy][nextDirection],
        dp[i][j] + 1
      );
    }
  }
}
 
console.log(dp[K][0] === Infinity ? -1 : dp[K][0]);
 

중요한건 다른 제식 행위를 각각 돌 수 있기 때문에 이에 따른 각도를 계속 계산해줘야 했다. dp 배열에는 내가 소모했던 에너지와 해당 배열 안쪽 nesting된 배열에는 해당 방향을 볼 때의 최소 깊이를 메모이제이션 해줘야 했다. 처음에는 모두 Infinity를 가진 4개의 배열을 dp배열에 채워주고, 삼중 for문을 돌면서 해당 에너지에서 몇번의 제식행동인지와 남은 각도를 기록하는 동시에 쵯솟값을 계속 갱신해줘야 했다.