[백준] 동적 프로그래밍 - 2193번 이친수 (Java)

문제링크

2193번: 이친수

 

접근한 방법

• 동적 프로그래밍

---

풀이방법

일단, 규칙을 찾는 데 집중했고 아래와 같은 규칙을 발견하였다.

N-1자리 이친수의 끝자리가 0이냐 1이냐에 따라 N자리 이친수의 개수가 정해진다.

 

N-1자리 이친수의 끝자리가 0이면 0과 1을 더 붙일 수 있다.

N-1자리 이친수의 끝자리가 1이면 0만 붙일 수 있다.

 

따라서, 점화식을 세워보면 아래와 같다.

• $a_{n,0}$ : n자리 이친수 중 끝자리가 0인 개수
• $a_{n,1}$ : n자리 이친수 중 끝자리가 1인 개수
• $a_{n}$ : n자리 이친수의 개수

$a_{n,0}$ = $a_{n-1,0} + a_{n-1,1}$

$a_{n,1}$ = $a_{n-1,0}$

 

∴ $a_{n}$ = 2 x $a_{n-1,0}$ + $a_{n-1,1}$

 

 

예시)

$a_{n}$	이친수 나열	이친수 개수	끝의 자리가 0인 개수	끝의 자리가 1인 개수
$a_{1}$	1	1	0	1
$a_{2}$	10	1	1	0
$a_{3}$	100 101	2	1	1
$a_{4}$	1000 1001 1010	3	2	1
$a_{5}$	10000 10001 10010 10101 10100	5	3	2
$a_{6}$	100001 100000 100010 100101 100100 101010 101001 101000	8	4	3

---

소스코드 작성 방법

• 2차원 배열로
  열의 0번 인덱스는 이친수의 끝자리가 0인 개수
  열의 1번 인덱스는 이친수의 끝자리가 1인 개수로 선언한다.
• a 배열의 크기를 [n+1][n+1]로 지정
• 결과값은 n-1까지만 알면되므로, 반복문을 i<n으로 돌린다.
• n이 1일 경우도 선언해준다.

 

실수한 점

• n이 90일 때, int범위를 벗어나는 것을 생각하지 못했다. 

n이 90일 때 이친수의 개수	2,880,067,194,370,816,120
int 범위	–2,147,483,648 ~ 2,147,483,647
long 범위	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

• 처음 a[2][0], a[2][1]도 초기화해두어 n이 1일 때 런타임 에러가 발생하였다.
• a 배열의 크기도 n으로 설정하였는데, 이것도 런타임 에러가 발생하였다. 이유는 모르겠다는 것이 함정..ㅠㅠ

 

 

소스코드

package baekjoon.dp;
import java.io.*;

public class Q_2193_PinaryNumber {
    public static long solution(int n){
        long[][] a = new long[n+1][n+1];

        a[1][0] = 0; a[1][1] = 1;

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

        if(n == 1)
            result = 1;
        else
            result = a[n-1][0] * 2 + a[n-1][1];

        return result;
    }

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

        int n = Integer.parseInt(br.readLine());
        bw.write(solution(n)+"\n");

        br.close();
        bw.close();
    }
}