프로그래머스 - 산 모양 타일링

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

프로그래머스

 

 

문제 해설

정삼각형과 정삼각형 두개를 이어붙인 사다리꼴을 이용해 주어지는 모양을 완성할 수 있는 모든 경우의 수를 구해야합니다.

먼저, tops[] 파라미터로 주어지는 그림을 배열로 표현해보겠습니다. 

위와 같은 그림은 아래와 같은 배열로 표현할 수 있습니다.

배열의 하나의 칸은 하나의 정삼각형을 의미합니다.

 

위 배열의 각 요소는 하나의 정삼각형을 의미함으로 인접한 칸과 사다리꼴로 합쳐질 수 있습니다.

여기서, 상층 삼각형의 존재 여부에 따라 사다리꼴로 만들어질 수 있는 경우의 수가 다르다는 점을 알 수 있습니다. 상층 삼각형의 존재 여부( tops[i] == 1, tops[i] == 0 )에 따라 이를 구분하고 각각의 경우에 사다리꼴로 합쳐질 수 있는 경우를 구해보겠습니다. 

상층 삼각형이 있는 경우에 나올 수 있는 경우의 수 4가지

 

상층 삼각형이 없는 경우에 나올 수 있는 경우의 수 3가지

 

 

tops를 이용해 각각의 경우를 나눔으로써 문제를 해결할 수 있을 줄 아셨겠지만, 문제를 풀기 위한 중요한 과제가 남아 있습니다.

바로,각각의 모형들은 하나의 작은 삼각형을 공유하고 있다는 점입니다.

tops에 따라 나눠진 모형들은 인접한 모형들끼리 하나의 삼각형을 공유하게 됩니다.

 

빨간 삼각형을 공유함에 따라 각각의 모형들은 독립적이지 않으므로 빨간 삼각형의 사용 여부에 따라 경우의 수를 나눠서 계산해야 할 필요가 있습니다. 이를 위해 두 가지 DP배열을 사용합니다. 또한, tops[i] == 1 인 경우와 tops[i] == 0 인 경우에 모형을 만들 수 있는 경우의 수가 다르다는 점을 인지하고 어떤 연산을 할지 생각해 봐야 합니다.

 

1. usedPreTriangleDP[] : 다음 빨간 삼각형을 사용하지 않는 경우의 수를 저장하는 DP배열 
   이전의 빨간 삼각형을 사용하지 않았을때, 다음 빨간삼각형을 사용하지 않는 경우의 수
   이전의 빨간 삼각형을 사용하지 않았을때, 다음 빨간삼각형을 사용하지 않는 경우의 수
   를 연산한 값을 저장
   
   
2. unusedPreTriangleDP[] : 다음 빨간 삼각형을 사용하는 경우의 수를 저장하는 DP 배열
   이전의 빨간 삼각형을 사용하지 않았을때,  다음 빨간삼각형을 사용하는 경우의 수
   이전의 빨간 삼각형을 사용했을때, 다음 빨간삼각형을 사용하는 경우의 수
   를 연산한 값을 저장
   

 

위에서 보여드린 그림을 이용해 아래 식을 천천히 이해해 보시기 바랍니다. 

 

<tops[i] == 1인 경우>

usedPreTriangleDP[i] = usedPreTriangleDP[i-1] * 1 + unusedPreTriangleDP[i-1] * 1

unusedPreTriangleDP[i] = usedPreTriangleDP[i-1] * 2 + unusedPreTriangleDP[i-1] * 3

 

<tops[i] == 0인 경우>
usedPreTriangleDP[i] = usedPreTriangleDP[i-1] * 1 + unusedPreTriangleDP[i-1] * 1

unusedPreTriangleDP[i] = usedPreTriangleDP[i-1] * 1 + unusedPreTriangleDP[i-1] * 2

 

 

이 문제를 풀때 모형 간 곂치는 삼각형에 대한 처리 방법을 긴 시간 고민했었습니다. 나눠지는 각각의 모형간의 연관관계를 명확히 인지하지 못했던 것이 아쉬움이 남고 이를 개선하기 위해 생각을 명확히 하는 연습이 필요한 것 같습니다. 추후에 여러 번 다시 풀어보며 체화할 수 있도록 해야겠습니다. 감사합니다.