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

문제

https://www.acmicpc.net/problem/1720

---

풀이(30분)

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N := 타일 코드의 개수
        int N = Integer.parseInt(br.readLine());

        // 전체 타일 코드 저장할 배열
        int[] dp1 = new int[31];
        // 좌우 대칭 타일 코드를 저장할 배열
        int[] dp2 = new int[31];

        dp1[1] = 1; dp1[2] = 3; dp1[3] = 5;
        dp2[0] = 1; dp2[1] = 1; dp2[2] = 3; dp2[3] = 1;

        for (int i = 4; i <= N; i++) {
            dp1[i] = dp1[i - 1] + (dp1[i - 2] * 2);
            dp2[i] = dp2[i - 2] + (dp2[i - 4] * 2);
        }

        int result = (dp1[N] - dp2[N]) / 2 + dp2[N];
        System.out.println(result);
    }
}

---

문제 풀이 전략

 

dp 자체의 규칙만 깨달으면 구현은 어렵지 않다.

사실 이건 대부분의 dp 문제가 다 그렇다고 생각한다.

 

규칙을 알아보자. 중요한 것은 좌우 대칭을 1개로 친다는 것이다.

 

그렇다면 여기서 문제가 발생한다.  좌우 대칭이 된다는 것은 되게 특수한 상황이다. 

좌우대칭 x -> 좌우대칭 o 도 가능하며 좌우대칭 o -> 좌우대칭 x도 가능하다. 

이러한 경우를 모두 어떻게 판단할까?

 

좌우 대칭과 관련된 네 가지 상황을 모두 생각해 보자.

 

1. 좌우 대칭이 아니었던 경우

• 추가되면 좌우 대칭이 된다.
  • 이 전 단계의 시작과 끝과 맞아야 한다.
• 추가되어도 좌우 대칭이 아니다.
  • 이 전 단계의 시작과 끝과 달라야 한다.

2. 좌우 대칭이었던 경우

• 추가되면 좌우 대칭이다.
  • 이 전 단계와 동일한 시작과 끝을 가져야 한다.
• 추가되어도 좌우 대칭이 아니다.
  • 이 전 단계의 시작과 끝과 달라야 한다.

복잡하게 정리되는 느낌이라 dp를 짜내기 어려웠다. 

dp1[i]에 대해서는 어렵지 않게 이해가 될 것이다.

dp2[i]에 대해서만 정리해 보면, 이 2단계 전의 값 + 4단계 전의 값*2가 된다.

2단계 전의 값이란 세로 기둥을 양쪽 끝에 붙일 수 있기 때문에 *1의 값이고, 4단계 전의 값이란 가로 2층 혹은 2x2 하나를 양쪽 끝에 붙일 수 있기 때문에 2배를 해주어 추가한다.

 

최종적으로 중복체크된 값을 제거해 주기 위한 연산을 한 뒤 출력한다.