백준 13301: 타일 장식물 [JAVA]

[문제 링크]

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

[난이도]

- Silver 5

 

[알고리즘]

- DP

 

[코드]

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());


        long[] dp = new long[n + 1];
        if (n == 1) {
            System.out.println(4);
        } else {
            dp[1] = 1;
            dp[2] = 1;

            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 2] + (dp[i - 1]);
            }

            System.out.println(dp[n]*4 + dp[n-1]*2);
        }

        br.close();
    }
}

[풀이]

피보나치 수열을 DP로 푸는 방식과 같다. 하지만 출력할 때 dp[n]*4 + dp[n-1]*2를 출력해주어야 한다.