[JS] 산 모양 타일링 (카카오 겨울 인턴십)

dp를 활용하여 해결할 수 있는 문제이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/258705

프로그래머스

 

 

이런 문제는 규칙을 찾는것이 중요하다.

 

해당문제와 같은 경우 조각이 추가되는 케이스가 2개다. 윗면이 있거나 없거나.. 

 

잘생각해보면 윗면이 있는 경우는 이렇게 생각할 수 있다.

 

먼저 

 

 

 

 

 

지금 추가되는 블럭을 i번째라고 생각해보자. 지금 추가한 3가지 블럭은 dp[i-1] 번째까지 블럭을 전혀 침범하지 않는다.

따라서 dp[i-1] * 3을 해주어서 경우의 수를 늘려줄 수 있다. 

 

dp[i-1] 번째 블럭의 경우의 수를 유지하면서 저 세조각의 모양을 붙여야 하기 때문에 *3을 해준다고 생각을 해줘도 된다. 만약 꼭대기 모양이 오지 않는경우라면 *2를 해주어야 한다. 단지 차이는 그 뿐이다.

 

문제는 아래 블럭이다.

 

이 블럭의 경우 dp[i-1] 번째의 경우의 수라고 할 순 없다. 이전 블럭에 단순히 더해지는 꼴이 아닌 이전 블럭의 맨 오른쪽 블럭을 한가지 써야하기 때문이다.

 

이 문제를 해결하기 위해서 dp블럭을 두개 두었다. 첫번째 dp는 바닥이 사다리꼴로 주어지는 (문제에서 요구하는) 경우의 수를 저장하는 블럭으로 두고 두번째 dp는 위 블럭을 해결하기 위해 맨 오른쪽 블럭이 없는 마름모꼴이 바닥인 상태의 경우의 수를 저장하도록 해주었다.

 

 

따라서 점화식이 아래처럼 나올 수 있다는 점은 이해할 수 있을 것이다.

const multi = tops[i - 1] ? 3 : 2;
dp[i] = (dp[i - 1] * multi + dp2[i - 1]) % 10007;

 

그렇다면 문제는 dp2의 점화식은 어떻게 구현되는가이다. 결국 바닥이 마름모꼴인 상태로 블럭이 붙여진다고 가정하는것 뿐 문제는 달라지지 않는다. 같은 방식으로 구해주면 된다.

 

 

( 그림은 조금 대충이지만.. )

dp랑 구할때랑 비슷하게 꼭대기가 있을때는 위와 같고 그렇지 않을때는 아래와 같다. 따라서 기본적으로 꼭대기가 있을때는 dp2의 이전 경우의 수의 *3 , 없을때는 *2를 하면 된다.

 

 

단 dp2를 구할때에도 마찬가지로 저번 영역을 침범하는 것이 일어난다.

 

 

위와같은 블럭 배치인 경우 2가지 경우의 수가 나옴을 알 수 있다. 그리고 빨간색 세모는 있던 없던 상관이 없다. 어차피 위와 같은 블럭 배치가 일어난 경우 빨간색 세모는 한개의 타일을 넣어야 할 수밖에 없기 때문

 

해당 부분을 뗀 나머지 부분은 밑바닥이 사다리꼴이된다. 즉 위 케이스는 dp에서 가져올 수 있다.

 

따라서 dp를 구할때는 dp2에서 , dp2를 구할땐 dp에서 가져오며 dp를 채워주는 것이 가능하다.

 

 

 

문제 풀이는 간단한데, 생각하는 과정이 조금 어려웠던 문제였다.

function solution(n, tops) {
  const dp = tops[0] === 1 ? [1, 4] : [1, 3]; // 밑바닥 사다리꼴모양
  const dp2 = tops[0] === 1 ? [0, 3] : [0, 2]; // 밑바닥 마름모모양

  for (let i = 2; i <= n; i++) {
    const multi = tops[i - 1] ? 3 : 2;
    const multi2 = tops[i - 1] ? 2 : 1;
    dp[i] = (dp[i - 1] * multi + dp2[i - 1]) % 10007;
    dp2[i] = (dp2[i - 1] * multi + dp[i - 2] * multi2) % 10007;
  }

  return dp[dp.length - 1];
}