🎈 삽질 과정
삽질도 많이했고, 다른 사람들의 풀이를 보면서도 이해하기까지 한참 걸렸던 문제다.
DFS로 풀어보려고 연결된 삼각형 클래스로 만들어서 리스트화 하고.. 재귀 돌리고..
하는 뻘짓을 하다 도저히 정답 근처에도 가지 못하는 것 같아서 다른 분들의 풀이를 참고했다.
풀어보면서 느낀 점은 도형이고, 규칙이 있어 보인다면 무조건 DP를 떠올릴 것!
구구절절 복잡하게 구조를 짜야하는 풀이가 떠오른다면 일단 다른 간단한 방법을 생각하도록 해야 할 것 같다.
📕 이해한 풀이
이 부분만 깨닫고 나니 점화식을 구하는 공식이 이해가 됐다.
핵심은 가운데 역삼각형 (문제에서 n개로 주어지는 것)을 채우는 방식이다.
모든 경우의 수를 나타내면 아래와 같다.
문제는 삼각형이 추가될 경우 겹치는 부분이 생긴다는 점이다.
특히 이전 삼각형에서 노란 타일(코드상에서RightDia)을 사용했을 경우 필연적으로 다음 삼각형과 오른쪽 아래 타일이 겹치게 된다.
따라서 이를 나누어서 계산해야 한다. (useRightDia,notUseRightDia)
맨 처음 삼각형의 경우 뚜껑 삼각형 여부와 관계 없이useRightDia일 때 1가지 경우의 수를 가진다.
그러나 뚜껑 삼각형의 여부에 따라notUseRightDia의 값은 달라진다.
이 원리를 계속해서 적용해 나가면 된다.
[i-1] 번째에서 채워진 부분을 제외하고 남은 부분을
모든 경우의 수에서 불가능한 타일들을 제외하며 찾다보면
사용한 점화식과 같은 규칙이 나온다.
using System;
public class Solution {
const int DIV = 10007;
public int solution(int n, int[] tops)
{
int answer = 0;
int[] useRightDia = new int[n];
int[] notUseRightDia = new int[n];
useRightDia[0] = 1;
notUseRightDia[0] = 2 + tops[0];
for (int i = 1; i < n; ++i)
{
useRightDia[i] = (useRightDia[i - 1] + notUseRightDia[i - 1]) % DIV;
notUseRightDia[i] = ((1 + tops[i]) * useRightDia[i - 1] + (2 + tops[i]) * notUseRightDia[i - 1]) % DIV;
}
answer = (useRightDia[n - 1] + notUseRightDia[n - 1]) % DIV;
return answer;
}
}