[level3][풀이안봄 알고리즘 분류 안봄] 아방가르드 타일링

level3 인데 정답률이 10프로이길래 의아해 하며 풀었다.. 생각보다 훨씬 까다로웠고 체감난이도는 백준에서  플레티넘1~2정도였다..

dp 계산할 때 index 경계값을 그냥 타일을 깔 때 나올 수 있는 경계의 경우의 수를 비트마스크로 단순하게 하면 쉽게 풀릴 줄 알았으나... 그 경계값을 정하는게 까다로웠다. 점화식을 세울 때 잘못 세우면 메모이제이션에서 중복된 값을 추가할 수 있기 때문이다..

이를테면 이것처럼 level 0일때,  level 1일때 중복되서 dp[1][2][3] 에 더하는 경우가 생길 수 있다. 

 

 

 

 

이 중복을 막기 위해서 어떻게 경계조건을 구하면서 더해야 할 것인가를 한참 고민하게 되었다.

 우선 가장 먼저 떠올 리기 쉬운 아이디어는 경계조건에서 블럭 하나를 추가 하는 방식이다.

그러나 위 사진에서는 경계의 차이 최대값이 4나 되고 그럼 다이나믹 프로그래밍 에서 성능이 느려질 수 밖에 없다.

그렇다면 경계의 값이 최대 3이게만 더하면 되지 않을 까라는 생각을 할 수 있다. 가장 길쭉한 블록이 3개 이므로 3개보다 클 경우에는 이미 다른 경우에서 최대값이 3이하이게 채워져 중복이 되지 않을까 하는 생각이 들 수 있다.

 

위와 같이 이미 3이하의 경계값에서 왼쪽에 길쭉한 블록을 더하게 되는 것이다.

그러나 이 방법도 문제가 있다.

블록을 하나씩만 더하게 된다면 아래와 같은 경우는 구할 수 없게 된다. 하나만 더하고 바로 level이 위로 올라가 버리기 때문이다.

 

그렇다면 최대 높이 차이가 3 이하가 되게만 되게 블록이 하나이든 두개이든 한번에 더하면 되지 않을 까? 라는 생각을 해보지만 역시 아까 언급했던 중복해서 더하는 문제에 걸리게 된다. 아래와 같은 문제이다.

 

 

또는 아래와 같을 때도 문제가 발생한다

level이 k 일때 높이가 k 일때 dp에 인덱스로 0을 넣는다고 치면, level이 k일때 기존에 dp[1][1][2] 이고 dp[3][2][2] += dp[1][1][2] 가 된다. 그런데 level 이 k + 1 일때에도 dp[2][1][1] +=  dp[0][0][1]  이 되게 된다.  

이걸 방지하려면 어떻게 해야 할지 생각하다가, 경계값에서 더할 때 기존의 경계값에서 높이가 0이 아닌 부분, 즉 솟아오른 부분에 블럭을 올려놓지 않으면 된다는 아이디어가 떠올랐다.

 

위이 경우는 아까 언급한 대로 중복이 되지만, 아래와 같이 level k일때 높이가 0인 부분에 블럭을 올린다면, level k+ 1 일때는 빨간색 블럭의 밑둥이 잘리므로 중복된 값을 더할 수 없게 된다. 즉 위의 그림일때는 level k일 때 ㄴ 형 블력이 다른 블럭위에 있어 k + 1일때도 밑둥이 잘리지 않아 중복적으로 더할 수 있지만,  아래와 같이 올린다면 더이상 중복이 불가능 하다.

인덱스 1부터 3까지 순회하면서 높이가 0인 부분일 때 ㄴ자 형 또는 일자 형으로 채우도록 재귀 형태로 코드를 짰다.

 

또 한가지 유의해야 할 점은 level k일 때 높이가 0인 부분이 한 부분도 없도록 하는 것이다. 그래야 k + 1 로 갈때 블럭이 공백인 부분이 없을 것이다. 

안되는 경우

 

level이 k일때 경계조건(검정색 부분)은 높이가 3일때 까지는 고려하지 않아도 된다. 높이가 3이된다면 블럭을 쌓을 때 (빨간색) 의 블럭과 중복이 된다.

위는 잘못된 예시고 위의 그림처럼 하게 된다면 dp[3][2][1]을 구할 때 아래의 그림처럼 블럭을 쌓을 때와 중복이 된다.

 

따라서 처음블럭값은 index0,1,2 에서 모두 높이 2인 완전탐색을 하고, 거기서 높이가 0인 부분만 블럭을 쌓게 한다면 중복없는 계산이 가능할 것이다.

 

위와 같이 밑둥이 잘리게끔 블럭을 쌓고 , 경계값(검정) 의 높이의 최댓값을      블럭으로 만들 수 있는 높이의 최댓값 - 1 로한다면, 위의 블럭 뿐만이 아닌 다양한 모양의 블럭이 있다고 하더라도 문제없이 다이나믹 프로그래밍으로 문제를 풀어나갈 수 있을 것이다