[백준2482_자바스크립트(javascript)] - 색상환

🔴 문제

색상환

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [n, k] = fs.readFileSync(path).toString().trim().split('\n').map(Number);

const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
const mod = 1000000003;

for (let i = 0; i <= n; i++) {
  dp[i][0] = 1;
  dp[i][1] = i;
}

for (let i = 2; i <= n; i++) {
  for (let j = 2; j <= k; j++) {
    dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1];
    dp[i][j] %= mod;
  }
}

const ans = (dp[n - 1][k] + dp[n - 3][k - 1]) % mod;
console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

dp 문제유형. 몰라서 풀이를 보고 풀었다.
색상환은 마지막에 겹쳐지는 부분을 제외하면 선형으로 생각하고 풀이할 수 있다.
dp 배열 다음과 같이 정의할 수 있다.

dp[i][j] : 총 i개의 색이 있을 때, j개의 색을 인접하지 않게 고르는 경우

위의 정의대로라면 색이 i개의 색이 있을때 0개의 색을 고르는 경우는 안고르는 경우 하나뿐이고, i개의 색이 있을 때 1개의 색을 고르는 경우는 i개의 경우가 있다.
따라서 초기값은 아래와 같이 지정할 수 있다.

for (let i = 0; i <= n; i++) {
  dp[i][0] = 1;
  dp[i][1] = i;
}

이제 색이 2개일 때부터 n개일 때까지의 dp배열을 채워준다.
색 1개를 고르는 경우는 초기값으로 지정해줬으니 색 2개를 고르는 경우부터 k개를 고르는 경우까지 반복한다.

색은 고르거나 안고르거나 두 경우로 나눌 수 있다.
만약 색을 고른다면 이전 색은 고르면 안된다.따라서 총 i개의 색 중에 선택한 색과, 선택한 색의 이전 색을 고르는 2가지 경우를 제외한 i-2개의 색 중 고를 수 있다. 또한 현재 색을 선택할 것 이므로 i-2개의 색 중에 j-1개를 선택하는 경우로 표현할 수 있다.
만약 색을 고르지 않는다면 i-1개의 색중에 j개를 선택한 경우로 표현할 수 있다.

위의 논리에 따른 점화식은 다음과 같다.

dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1];

다만 마지막에 원형으로 이어지는 경우의 수를 고려해줘야 한다.
마지막 색을 고르지 않을 경우는 n-1개의 색 중 k개를 고르는 경우로 표현할 수 있다.
마지막 색을 고르는 경우는 이전 색 뿐만 아니라 다음색도 겹쳐지는지 확인해줘야 한다. 따라서 선택한 현재 색과 이전 색, 다음 색을 제외한 n-3개의 색 중 k-1개를 선택한 경우로 표현할 수 있다.

🔵 Ref

https://akim9905.tistory.com/71