[백준][2193번] 이친수

문제 URL

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

나의 풀이

package backjoon;

import java.io.*;

public class Main {
    public static final int mod = 1000000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] d = new long[n + 1][2];
        //d[N][L] = 길이가 N인 계단수, 마지막수 L

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

        System.out.println(d[n][0] + d[n][1]);
    }
}

느낀점

동적계획법 을 이용한 문제다.

큰수를 계속 더해서 int 범위를 넘어버려 오류가 발생했다. 그래서 long형으로 바꿔서 해결했다.

• 연속이라는 조건을 처리할때는 2차원 배열 활용 할수있다.!!

• 1차원배열로도 가능하다.
  D[N] = N자리 이천수 1) 마지막수 0 이면

  • n-1은 0,1 모두 올수있다. -> D[n-1] 2) 마지막수 1 이면
  • n-1은 0만올 수 있고 n-2는 0,1이 올수있다. -> D[n-2] => D[n] = D[n-1] + D[n-2]