[백준] 2193번. 이친수(JAVA)

문제

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

---

풀이(18분)

import java.io.*;
import java.util.*;

public class Main {


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

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        long[][] arr = new long[n+1][2];

        if(n == 1 || n == 2){
            System.out.println(1);
            return;
        }

        arr[1][0] = 1;
        arr[1][1] = 1;


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

        System.out.println(arr[n-2][0] + arr[n-2][1]);


    }
}

 

문제를 봤을 때 DP라는 것은 감을 잡았다. 다만 점화식을 세우는 부분에 있어 고민을 했다.

다음과 같은 아이디어를 통해 점화식을 세웠다.(long자료형을 쓴 이유는 점화식을 따라가면서 설명하겠다.)

 

점화식을 세우기 전에 먼저 몇개의 예시를 직접 작성해보자.

n = 1 : 1

n = 2 : 10

n = 3 : 100, 101

n = 4 : 1000, 1001, 1010 

이런 식으로 진행된다. 또한, dp 문제를 풀며 가장 중요한 부분인 예시를 만들 때 본능적으로 편하게 작성하는 아이디어를 꼭 기억해두자. 

 

이 예시를 세우며 쓴 편하게 만드는 법은 다음과 같다.

1. n = 1, 2는 어쩔 수 없다. 그냥 하자.

2. 앞에 10은 무조건 고정이구나?

3. 뒤에 이 전 단계의 숫자를 기반으로 할 때 0으로 끝났으면 0과 1 둘 다 붙일 수 있고, 1이면 무조건 0을 붙여야 하겠구나.

 

위의 아이디어를 코드로 구현하면 됐다!

꼭 기억하자. 점화식이란 물론 식을 세우기 위한 생각을 해야하는 것일 수도 있지만, 결국 내가 편한 방식으로 생각하는 것이 80%정도는 좋은 점화식이 될 수도 있다!!!