BJ S2 2133 타일채우기

BJ S2 2133 타일채우기

 

 

문제링크

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

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/CJ7C0wQVxCI

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Scanner;

/**
 * @author itsmeyjc
 * @since 2020. 4. 17.
 * @see https://www.acmicpc.net/problem/2133
 * @mem 14272
 * @time 108
 * @caution #dp
 */
public class BJ_S2_2133_타일채우기 {

    static int N;
    static int[] memo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        N = Integer.parseInt(br.readLine());

        memo = new int[N + 1];
        memo[0] = 1;

        for (int i = 2; i <= N; i += 2) {
            memo[i] = memo[i - 2] * 3; // 기본적으로 2 칸을 채우는 방법은 3가지가 존재
            for (int j = i - 4; j >= 0; j -= 2) {
                memo[i] += memo[j] * 2; // 이전 두 칸마다 두 가지 경우가 더 발생하게됨
            }
        }
        System.out.println(memo[N]);
    }


    static String src = "50";
}