[백준] JAVA 자바 : 2×n 타일링 (11726번)

---

사실 이 문제 이전에 나온 1로 만들기 문제는 못 풀어서 구글링해서 겨우 풀었는데…ㅋㅋ
DP 알고리즘을 한 번 이해하고 나니까 이런 문제 정도는 굉장히 쉽게 풀리는 듯?

아직 실버3 수준이라서 그런지… 조금만 사고하면 어렵지 않게 풀 수 있다.

DP알고리즘의 여느 때처럼 이전 값들을 저장할 수 있는 배열을 만들어준 다음 0번째 인덱스와 1번째 인덱스에 1을 할당한다. (초깃값 설정)

이후 Bottom-Top 방식을 채용해서 i를 2부터 X까지 반복시키면서
dp[i]에는 dp[i-1] + dp[i-2], 즉 1×2로 채우는 방식 + 2×1로 채우는 방식의 경우의 수를 더해주면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Tiling_2n {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

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

        int X = stoi(br.readLine());

        long[] dp = new long[X+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i=2; i<=X; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }

        System.out.println(dp[X]);
    }
}

 

로그인

 

 

작성일자: 2023-11-24