🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split(' ').map(Number);
const getEnergy = (a, b) => {
if (a === b) return 1;
if (a === 0) return 2;
if (Math.abs(b - a) % 2 === 0) return 4;
else return 3;
};
const n = inputs.length - 1;
const dp = Array(n)
.fill()
.map(() =>
Array(5)
.fill()
.map(() => Array(5).fill(false))
);
const dfs = (step, l, r) => {
if (step >= n) return 0;
if (dp[step][l][r]) return dp[step][l][r];
const moveLeft = dfs(step + 1, inputs[step], r) + getEnergy(l, inputs[step]);
const moveRight = dfs(step + 1, l, inputs[step]) + getEnergy(r, inputs[step]);
dp[step][l][r] = Math.min(moveLeft, moveRight);
return dp[step][l][r];
};
console.log(dfs(0, 0, 0));🟢 풀이
⏰ 소요한 시간 : -
DP유형!!
문제 보자마자 DP인지, 3차원 배열을 써야하는지, 왼발로 나아갔을 때와 오른발로 나아갔을 때의 최소 값을 DP에 저장해야된다...! 를 알고 있었는데 구현을 못해서 풀이봤다...! 풀이를 봐도 이해하기 어려웠는데 나랑 가장 잘 맞는 풀이를 찾아 해결했다. DP와 DFS를 결합한 풀이다.
먼저 현재 위치에서 다음 위치로 발을 옮겼을 때 드는 에너지 값을 계산하는 getEnergy 함수를 만들어 준다. a에서 b로 갈 때 값을 리턴해주는 함수다.
그 후 입력길이에서 지시사항이 몇 번있는지를 n에 저장한다. 그 후 길이가 n인 dp배열을 만드는데, 각 요소는 5 x 5 크기의 배열로 채워준다. 내부의 배열은 왼발과 오른발이 각각 몇번 발판을 가지고 있는지 확인하는 배열이다.
위와 같이 아래로 내려가는 행은 왼발이 밟고 있는 숫자 번호, 열은 오른발이 밟고 있는 숫자 번호로 25칸의 배열을 만들고, 이를 n번의 depth로 만들어 주면 된다.
그 후 반복해서 0단계 그리고 왼쪽 오른쪽 모두 0번발판을 밟고 시작하므로 dfs(0, 0, 0)로 dfs를 수행한다.
dfs의 내부를 보면, 먼저 step이 n보다 커지면 0을 리턴하여 재귀를 종료한다. 만약 dp[step][l][r]가 false가 아니라면 이미 방문하고, 계산을 마친 상태이기 때문에 메모제이션 한 값을 리턴한다. 그게 아니라면 dp 배열을 채워주면 되는데, 현재 step에서 왼발로 나아간다면 step을 1 증가시킨 값과, 목표 발판인 inputs[step], 그리고 오른발은 고정이므로 dfs(step + 1, inputs[step], r)를 호출한다. 왼발을 이동시켰으므로 에너지도 갱신한다. 오른발도 동일하게 값을 구해준다.
그리고 왼발을 움직였을 때와 오른발을 움직였을 때 중에서 더 적은 에너지를 소모하는 쪽을 선택하여 현재 dp 값을 갱신한다. 그리고 그 값을 리턴해주면 다음 재귀에서 사용할 수 있다.
🔵 Ref
