[Java] 백준 11726번 : 2×n 타일링 <Silver 3>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

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

11726번: 2×n 타일링

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    void run() throws IOException {
        int num = Integer.parseInt(bf.readLine());
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1,2));

        int result = find(num, arr);

        System.out.println(result);
    }

    int find(int n, ArrayList<Integer> arr){
        int number = 2;
        while (true){
            if(n < 3){
                return arr.get(n-1);
            }
            number++;
            arr.add((arr.get(number - 2) + arr.get(number - 3))%10007);
            if(number == n){
                return arr.get(number-1);
            }
        }
    }

    public static void main(String[] args) {
        Main my = new Main();
        try{
            my.run();
        }catch(Exception e){}
    }
}

---

Code 필수 요소

1. Dynamic Programming(동적 프로그래밍) 사용

2. 규칙 찾기

 

// Dynamic Programming(동적 프로그래밍) 사용

한동안 계속해서 풀 예정인 Dynamic Programming문제의 핵심은 이 문제가 Dynamic Programming을 사용해야 한다는 것을 깨닫는 것이다. 

 

// 규칙 찾기

이 문제의 경우 규칙은 단순했다. 2X1인경우 당연히 경우의 수는 1이고, 2X2인 경우 경우의 수는 2이다. 이건 당연한 것이므로 설명은 생략한다. 2X3일 경우 3, 2X4일경우 5, 2X5일경우 8이다. 즉, X = (X-1) + (X-2)의 규칙이 있다.

 

// 전체적 설명

바텀업 방식을 사용하여 ArryList에 해당하는 값을 하나씩 저장하며 해당 값에 접근한다.

 

동적 계획법이란?

https://naemamdaelo.tistory.com/27

알고리즘 - Dynamic Programming(동적 계획법)

사실상 동적 계획법 문제들은 이 문제가 동적계획법을 사용하는지, 그리고 어떤 규칙이 있는지를 파악하면 끝나기 때문에 쉬우면서 어려운 문제라고 생각한다.

 

-꿑-