[백준 1720번] 타일 코드 (java)

1720번: 타일 코드

 

이 문제는 다이나믹 프로그래밍으로 풀었다.

좌우대칭인 한 결과는 동일한 것으로 간주해야 한다는 점에서 처음에 점화식을 세우기 어려웠다.

 

만약 좌우대칭을 신경쓰지 않는다면 점화식을 다음과 같이 세울 수 있다.

dp[n] = dp[n-1] + dp[n-2] * 2

 

타일의 가로 길이가 n일 때의 가능한 경우의 수는

① 타일의 가로 길이가 n-1일 때에서 2x1짜리 타일을 하나 추가한 경우 -> dp[n-1]

② 타일의 기로 길이가 n-2일 때에서 2x2짜리 타일이나 1x2짜리 타일 2개를 추가한 경우 ->dp[n-2] * 2

를 합친 것이 된다.

 

최종적으로 dp[N]은 가로 길이가 N일 때 가능한 모든 경우의 수가 들어간다.

 

그렇다면, 문제 조건대로 좌우 대칭을 이루는 경우를 하나의 경우로 간주하기 위해서는

전체 경우의 수(dp[N])에서 좌우 대칭인 경우를 뺀 후, 2로 나눈 후, 다시 좌우 대칭인 경우를 더하면

답을 구할 수 있다.

 

무슨 말인가 하면,

만약 N = 4 인 경우 좌우 대칭을 고려하지 않는 모든 가능한 경우의 수는 아래의 그림처럼 총 11가지이다. dp[4] = 11

 

 

여기서 좌우대칭인 경우는 아래 그림에서 회색으로 칠한 경우이다.

좌우 대칭인 경우를 제외하면 나머지 6가지가 존재한다. 그리고 이 6가지는 좌우를 바꿨을 때 같은 모양이 되는 것이 3쌍 존재하는 꼴이 된다.

 

 

분홍색은 분홍색끼리 좌우 변환 시 동일하고, 하늘색은 하늘색끼리 좌우 변환 시 동일하며, 초록색은 초록색끼리 좌우 변환 시 동일하다.

색상이 동일한 것들은 모두 하나의 경우로 간주해야 하므로 6가지에서 2로 나눠야 한다.

6 / 2 = 3 가지

 

 

 

그리고 이 3가지에서 아까 회색 처리한 좌우 대칭인 경우의 수 5가지를 더한다.

3 + 5 = 8가지

최종적으로 N = 4 일 때, 문제에서 요구하는 경우의 수는 8가지가 된다.

 

 

그렇다면 N = 4일 때, 좌우 대칭인(회색 부분) 모든 경우의 수를 구하는 과정이 필요하다.

나는 2차원 배열 dp2를 생성하여 좌우 대칭인 경우의 수를 저장하는 메모이제이션을 수행했다.

2차원 배열의 두 인덱스는 구하고자 하는 구간(가로의 i부터 j까지)을 의미한다.

 

dp[i][j] = dp[i+1][j-1] + dp[i+2][j-2]*2

 

 

위 점화식 대로라면 가로길이가 N일 때의 좌우 대칭인 모든 경우의 수는 dp2[1][N]가 될 것이다.

따라서 최종 구하고자 하는 값은 다음과 같다.

result = (dp[N] - dp2[1][N]) / 2 + dp2[1][N];

 

 

N이 짝수일 때와 N이 홀수일 때를 나눠서 초기값을 정해야 한다.

 

N이 홀수일 때는 가장 가운데의 한칸짜리부터 좌우로 구간을 넓혀가며 메모이제이션을 한다.

N이 짝수일 때는 가장 가운데의 두칸짜리부터 좌우로 구간을 넓혀가며 메모이제이션을 한다.

 

 

N이 홀수일 때는

dp2[N / 2 + 1][N / 2 + 1] = 1;
dp2[N / 2][N / 2 + 2] = 1;

 

N이 짝수일 때는

dp2[N / 2][N / 2 + 1] = 3;   

dp2[N / 2 - 1][N / 2 + 2] = 5;

 

 

 

전체 코드 :