[프로그래머스] 아방가르드 타일링 (C++)

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

프로그래머스

 

[문제 요약]

• 90도씩 회전이 가능한 두개의 도형으로 만들 수 있는 3 * n 의 타일의 개수를 구하는 문제.

 

[풀이]

• O(N)에 풀리는 DP문제
• 두 도형을 90도씩 회전해 가면서 만들 수 있는 도형의 규칙성을 찾는다.
  
  • 3 * 1인 경우는 1개
  • 3 * 2인 경우는 3 * 1 + 3 * 1을 제외한 2개를 만들 수 있다.
  • 3 * 3인 경우는 2 + 1, 1 + 2를 제외한 5개를 만들 수 있다.
  • n이 4 이상인 n * 3 타일 또한 새로운 모양의 타일을 만들 수 있다.도형을 회전해 보면 4인 경우 2개, 5인 경우 2개, 6인 경우 4개인 것을 알 수 있다.
  • 4인 경우에서 7인 경우는 3 * 1 타일이 중간에 들어가면 된다. 5, 6인 경우에도 동일하다.
  • 따라서 4 + 3k, 5 + 3k인 경우 새로운 조합의 타일이 2개씩, 6 + 3k인 경우 4개가 생긴다.

n = 4, 5, 6인 경우 새로 만들 수 있는 도형.

90씩 회전을 하면 4인 경우 2가지, 5인 경우 2가지, 6인 경우 6가지가 나온다.

4 + 3k, 5 + 3k, 6 + 3k 인 경우 중간에 1 * 3의 도형들이 k개씩 추가 되며, 각 2 2 4의 새로운 도형을 만들 수 있다.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

long long dp[100002] = { 1, 1, 3, 10, 23, 62, 170, };
long long sum[100002] = { 1, 1, 3, 11, 24, 65, 181, };

const int INF = 1e9 + 7;

int solution(int n) {
	for (int i = 7; i <= n; i++) {
		dp[i] = dp[i - 1];
		dp[i] += dp[i - 2] * 2;
		dp[i] += dp[i - 3] * 5;
		dp[i] += sum[i - 4] * 2;
		dp[i] += sum[i - 5] * 2;
		dp[i] += sum[i - 6] * 4;
		dp[i] %= INF;

		sum[i] = dp[i] + sum[i - 3];
		sum[i] %= INF;
	}

	return dp[n];
}

 

[코드 설명]

• 새로운 도형에 대해서 새로운 조합의 타일을 만들어야 한다.
  예를 들어 n = 2인 타일은 3가지 경우가 있지만, 3 * 1 + 3 * 1인 경우는 새로운 타일이 아니다.
• 점화식은 다음과 같다.
  F(n) = F(n - 1) + F(n - 2) * 2 + F(n - 3) * 5 + sum(F(n - 4 - 3k)) * 2 + sum(F(n - 5 - 3k)) * 2 + sum(F(n - 6 -3k)) * 4
• n <= 100,000인 문제이기 때문에 부분합 배열을 하나 만들어 준다.
• 3 * n 타일 개수와 sum(3 * (n - 3k))의 타일 개수의 합을 저장해두고 한번에 연산한다.