[알고리즘 PS] 백준 11727번 2*n 타일링 2 자바 문제 풀이

문제

해당 포스팅은 백준의 문제 이름 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 지난 2n 타일링1문제와 아주 비슷한 문제이다.

대충 출제 의도를 생각해보면 2n 타일링이 피보나치 수열의 값과 똑같아서 해당 문제를 피보나치로 풀었는지 혹은 정확히 문제 출제 의도를 파악하고 풀었는지를 확인하는 문제같다.

접근법

지난 2n 타일링에서는 2가지 종류의 타일이 존재했지만 이번 2n 타일링에는 3가지 종류의 타일이 존재한다.

1. 1 x 2 타일
2. 2 x 1 타일
3. 2 x 2 타일

지난 문제의 접근과 비슷하게 이번에도 각각의 경우를 n-1 번째 단계, n-2번째 단계에서 찾아볼 수 있다.

 

지난 문제와 다른 점이 있다면 2 x 2 타일이 추가 되었다는 것인데,

2 x 2 타일은 1 x 2 타일 2개와 비슷한 모양으로 대체될 수 있다.

이 말은 1 x 2 타일이 들어갈 수 있는 a(n-2)에 경우의 수가 2번 반복될 수 있다는 소리이다.

 

이 것을 점화식으로 바꿔보면,

1. 2 x (n-1) 번째 타일에서 2 x 1 타일이 추가된 경우
2. 2 x (n-2) 번쨰 타일에서 1 x 2 타일이 2개 합쳐진 형태의 타일이 추가된 경우
3. 2 x (n-2) 번쨰 타일에서 2 x 2 타일이 추가된 경우

오답 후보

이번에도 역시 모듈러 연산에 주의해야 한다.

정답 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[1001];

        arr[1] = 1;
        arr[2] = 3;

        for (int i = 3; i <= n; i++) {
            arr[i] = (arr[i-2] * 2) + arr[i-1];
            arr[i] %= 10007;
        }

        bw.write(String.valueOf(arr[n]));
        bw.flush();
        bw.close();
    }
}

---

문제 회고

이번 문제는 지난 2 x n 타일링에서 배운 먹은 스킬을 사용할 수 있었다.

하지만 아직 점화식의 특성을 이해하지 못한 것인지 계속 중복에 대해서 신경쓰게 된다.

중복에 대한 신경을 쓴다는 것은 점화식 특성을 확실히 이해하지 않은 것으로 생각된다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.