🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
.readFileSync(path)
.toString()
.trim()
.split('\n')
.map((it) => it.split(' ').map(Number))
.flat();
const t = inputs.shift();
const w = inputs.shift();
const dp = Array.from({ length: t }, () => Array(w + 1).fill(0));
for (let i = 0; i <= w; i++) {
if (inputs[0] === 2) {
if (i % 2 === 1) dp[0][i] = 1;
else dp[0][i] = 0;
} else {
if (i % 2 === 1) dp[0][i] = 0;
else dp[0][i] = 1;
}
}
for (let i = 1; i < t; i++) {
if (inputs[i] === 1) dp[i][0] = dp[i - 1][0] + 1;
else dp[i][0] = dp[i - 1][0];
for (let j = 1; j <= w; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
if (j % 2 === 0 && inputs[i] === 1) dp[i][j] += 1;
else if (j % 2 !== 0 && inputs[i] === 2) dp[i][j] += 1;
}
}
console.log(Math.max(...dp[t - 1]));🟢 풀이
⏰ 소요한 시간 : -
dp 테이블 설계하기가 쉽지 않아서 풀이를 봤다.
딱 dp 테이블만 참고했다 ...
이 사진을 보고 어떻게 설계를 했냐면 ..
T초의 크기를 가지는 dp 배열을 설계하고 각 dp 배열 내부에는 0번이동 부터 w번이동까지의 크기를 가지는 배열을 설계했다.
문제 예시로 따지면 7초동안 w번 이동 가능이니까 아래와 같은 2차원 배열을 만들어준다.
dp[0] = [0, 0, 0]
dp[1] = [0, 0, 0]
dp[2] = [0, 0, 0]
dp[3] = [0, 0, 0]
dp[4] = [0, 0, 0]
dp[5] = [0, 0, 0]
dp[6] = [0, 0, 0]내부 배열의 크기가 3칸인 이유는 0번 이동, 1번 이동, 2번 이동의 값을 채우기 위함이다.
내부 배열안의 값은 내가 현재 자두를 몇개 받았는지를 나타내는 값이다.
dp[0]일때 초기값을 채워넣어보자! 참고로 0번째 인덱스가 1초라고 가정했다. 모든 인풋값과 dp배열이 0번째 인덱스 부터니까 ...!
1초(dp[0])일때는 내가 1번 나무에 있거나 2번 나무에 있거나 둘 중 하나인데 이 때 0, 2, 4 이렇게 짝수번째 인덱스는 1번 나무에 있는 것이고 1, 3, 5 등 홀수번째의 인덱스는 2번나무에 있는 것이다. 그래서 초기값은 inputs[0]이 1인지, 2인지에 따라 달라진다.
이 후 2초(dp[1])일때부터 t초일때까지 dp 배열을 채워주면 된다.
만약 0번 이동했다면 즉 이동하지 않았다면 바로전에 메모된 값을 사용한다. 사실 0번 이동했다면 무조건 1번 나무에 서있을 테니까 inputs[i] 즉 현재 사과가 떨어지는 위치가 1이라면, 1을 더해준다.
그 후 1번부터 w번 이동횟수는 반복문을 돌면서 조건을 따져주는데, dp[i][j]는 바로 전 단계에서 같은자리에 그대로 서있거나, 바로 전 단계에서 건너오거나 둘 중 하나이다. 이 때 건너오려면 j-1번 이동했을때로부터 j번 이동으로 건너오는 것이기 때문에 dp[i - 1][j], dp[i - 1][j - 1] 두 개의 값중 최대값을 넣어준다.
마지막으로 dp[i][j]위치에서 j가 짝수라면 사과가 1번에서 떨어졌을 때 1을 더해줘야 하고, j가 홀수라면 사과가 2번에서 떨어졌을 때 1을 더해줘야 한다.
정답은 dp배열의 t초(dp[t-1])에서 최대값을 골라주면 된다.
🔵 Ref
