문제

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

정우는 예술적 감각이 뛰어난 타일공입니다. 그는 단순한 타일을 활용하여 불규칙하면서도 화려하게 타일링을 하곤 합니다.

어느 날 정우는 가로 길이 n, 세로 길이 3 인 판을 타일링하는 의뢰를 맡았습니다. 아방가르드한 디자인 영감이 떠오른 정우는 다음과 같은 두 가지 종류의 타일로 타일링을 하기로 결정했습니다.

각 타일은 90도씩 회전할 수 있으며 타일의 개수는 제한이 없습니다.

n이 주어졌을 때, 이 두 가지 종류의 타일로 n x 3 크기의 판을 타일링하는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

입력

• 1 ≤ n ≤ 100,000

출력

• 결과는 매우 클 수 있으므로 1,000,000,007 로 나눈 나머지를 return합니다.

예

n = 2

n = 3

풀이

주어진 타일 가지고 어떤 규칙에 의해서 3*N 형태의 모양을 만들 수 있는지 찾는 게 관건이다. 규칙을 찾으려면 주어진 문제 조건 대로 타일을 만들고 분석을 해본다.

• n = 1
  3*1 형태 새 타일 유형 1개
  [여기서 새로 나온 타일을 (a) 형태라 지정 한다.]
  총 1개
• n = 2
  (a) 형태 & 나머지 3X1로 되는 경우의 조합(=1X1)개 +
  3*2 형태 새 타일 유형 2개
  [여기서 새로 나온 타일을 (b) 형태라 지정 한다.]
  총 3개
• n = 3
  (a) 형태 & 나머지 3X2로 되는 경우의 조합(=1X3)개 +
  (b) 형태 & 나머지 3X1로 되는 경우의 조합(=2X1)개 +
  3*3 형태 새 타일 유형 5개
  [여기서 새로 나온 타일을 (c) 형태라 지정 한다.]
  총 10개
• n = 4
  (a) 형태 & 나머지 3X3로 되는 경우의 조합(=1X10)개 +
  (b) 형태 & 나머지 3X2로 되는 경우의 조합(=2X3)개 +
  (c) 형태 & 나머지 3X1로 되는 경우의 조합(=5X1)개 +
  3*4 형태 새 타일 유형 2개
  [여기서 새로 나온 타일을 (c) 형태라 지정 한다.]
  총 23개
• n = 5
  …
• n = 6
  …

n을 늘려가면서 무슨 규칙이 보이는가? 아직은 보이지 않는다. 그나마 알 수 있는 것이 n이 늘어가면서 새로운 형태의 타일 조합 유형이 나오고 있는 것이다. 거기에만 집중해서 새로 생기는 타일 유형의 패턴을 파보도록 한다.

n이 1, 2, 3일 때 생기는 타일 유형은 불규칙하지만, n = 4,5,6 일 때부터 2,2,4개씩 새로 생성이 된다. n=4,5,6인 유형의 타입 중간 중간에 1*3 타일을 한 행마다 한개씩을 끼워 넣는다면 형태는 비슷하게 생겼지만 새로운 유형의 타일이 생기게 될 것이다. 그래서 1,2,5, 2,2,4, 2,2,4, 2,2,4… 이런식으로 규칙을 발견할 수 있다.

그러면 이제 새로 생기는 유형 패턴은 알았으니, 이전의 유형을 이용하는 구간을 까지 알아본다. N일때 타일의 개수는 (N-1)타일로 만드는 경우의 수 X (3X1) 유형의 타일의 경우의 수 + (N-2)타일의 경우의 수 X (3X2) 유형의 타일의 경우의 수 + … + 1타일로 만드는 경우의 수 (3*(N-1)) 유형의 타일의 경우의 수 + 새로 생기는 경우의 수 일 것이다. 이를 수식으로 표현 하면…

dp[i]: 3*n 일때 조건대로 놓을 수 있는 가지 수

dp[i] = dp[i-1] X 1 + dp[i-2] X 2 + dp[i-3] X 5 + 
        dp[i-4] X 2 + dp[i-5] X 2 + dp[i-6] X 4 + 
        dp[i-7] X 2 + dp[i-8] X 2 + dp[i-9] X 4 + 
        ...

위와 같이 될 것이다. 나름 잘 정의는 했는데… 좀 줄여보자… 규칙이 4번째 항부터 2,2,4 로 반복되니, dp[i]의 i를 i-3으로 치환해본다. 그러면

dp[i-3] = dp[i-4] X 1 + dp[i-5] X 2 + dp[i-6] X 5 + 
          dp[i-7] X 2 + dp[i-8] X 2 + dp[i-9] X 4 + 
          ...

이렇게 표현할 수도 있다. 그럼 여기서 dp[i] - dp[i-3] 을 해보면…

dp[i] - dp[i-3] = dp[i-1] X 1 + dp[i-2] X 2 + dp[i-3] X 5 +  
                  dp[i-4] X 1 + dp[i-5] X 0 - dp[i-6] X 1

dp[i] = dp[i-1] X 1 + dp[i-2] X 2 + dp[i-3] X 6 + dp[i-4] X 1 - dp[i-6] X 1

이라는 최종 식이 나오게 된다. 정리된 식을 코드로 옮기면 끝이다.

public int solution(int n) {
  int mod = 1000000007;
  long[] dp = new long[100001];
  
  dp[1] = 1; 
  dp[2] = dp[1] * 1 + 2; 
  dp[3] = dp[2] * 1 + dp[1] * 2 + 5;
        
  dp[4] = dp[3] * 1 + dp[2] * 2 + dp[1] * 5 + 2;
  dp[5] = dp[4] * 1 + dp[3] * 2 + dp[2] * 5 + dp[1] * 2 + 2;
  dp[6] = dp[5] * 1 + dp[4] * 2 + dp[3] * 5 + dp[2] * 2 + dp[1] * 2 + 4;

  if(n <= 6){
    return Long.valueOf(dp[n]).intValue();
  }
        
  for(int i = 7; i <= n; i++){
    dp[i] = (dp[i-1] + dp[i-2] * 2 + dp[i-3] * 6 + dp[i-4] - dp[i-6]) % mod;
    if(dp[i] < 0){
      dp[i] += mod;
    }
  }
        
  return Long.valueOf(dp[n]).intValue();
}

추가적으로 주의해야 할 점은 int 유형의 값이 overflow될 수도 있으니 이보다 큰 유형인 long으로 바꿔줘야하는 것이 있고, dp[i]의 결과는 1,000,000,007 로 나눈 결과이기 때문에 구한 점화식에서 음수가 나올 수도 있다. 그래서 음수인 경우에도 처리가 되야 한다.

결론

중딩 혹은 고딩때 수학이란 과목에서 문제를 풀다가 골치 아파지는 기억들이 있을 것이다. 그러한 기억들 중 하나의 예시를 들자면, 어떤 수열이 있고 이 수열에 대한 규칙을 찾아서 특정한 답을 도출하는 문제일 것이다. 이러한 문제를 지금 나이에 개발하면서 까지도 이어져 온다. 규칙 찾는 팁은 두가지이다. 졸라 많이 풀고, 두뇌를 풀 가동해야 한다. 단순하면서도 고단한 방식이자 정석적인 방식인 것이다. 그리고 추가적으로 문제를 잘 파악해본다. 함정이 숨어져 있을 것이다.