[백준-2193]-[다이나믹프로그래밍] - 이친수

문제링크 : https://www.acmicpc.net/problem/2193

이 문제는 흠.. 좀 여기에 정리해 가면서 풀어봐야겠다. 

머리가 딸리니 연습장에 그려가면서 하기엔 악필이라 영 내가 알아보기가 힘들다 

어느정도 풀이법이 보인다. 

하나 하나 정리해가면서 해봐야지

자 친절하게 문제에서 이친수가 무엇인지 설명을 해주었다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

위의 두 조건은 잊지 말아야지.

그리고 N 자리 이친수가 몇개 존재하는지 알아봐 달라고 한다.  별걸 다 알고 싶어하네 또다시 빡친다.

그래도 뭐 풀어야지

일단 자리수 별로 이친수를 구해보면서 규칙을 찾아봐야겠다. 

1 자리는 

1 

2 자리는 

1 0

3 자리는 

1 0 0 

1 0 1

4 자리는 

1 0 0 0

1 0 0 1 

1 0 1 0

5 자리는 

1 0 0 0 0 

1 0 0 0 1 

1 0 0 1 0

1 0 1 0 0

1 0 1 0 1

6 자리는

1 0 0 0 0 0

1 0 0 0 0 1

1 0 0 0 1 0

1 0 0 1 0 0

1 0 0 1 0 1

1 0 1 0 0 0

1 0 1 0 0 1

1 0 1 0 1 0

처음엔 5자리까지는 음 개수가 n-1의 자리수 * 2 -1 cnt[n-1] * 2 -1 이겠구나 오 쉽겠다 생각했는데

6자리 오니깐 역시나 아니었다. 

그럼 이제 어떻게 풀어야 할까 고민을 해보다가 끝자리를 0 끼리 1 끼리 따로 빼보았다. 

6자리의 이친수들 중 끝자리가 0으로 된것들은

1 0 0 0 0 0

1 0 0 0 1 0

1 0 0 1 0 0

1 0 1 0 0 0

1 0 1 0 1 0

총 5개

6자리의 이친수들 중 끝자리가 1로 된것들은

1 0 0 0 0 1

1 0 0 1 0 1

1 0 1 0 0 1

총 3개

워매?? 보인다 나누니깐 보인다 그럼 표를 그려보면서 자세히 보자.

일단 참고로 할 4자리와 5자리의 이친수도 표로 그리고 6의 이친수를 그려보면서 제대로 분석해보자.

4의 이친수 표

1	1	0	0	0
2	1	0	1	0
3	1	0	0	1

5의 이친수 표

1	1	0	0	0	0
2	1	0	0	1	0
3	1	0	1	0	0
4	1	0	0	0	1
5	1	0	1	0	1

6의 이친수 표

1	1	0	0	0	0	0
2	1	0	0	0	1	0
3	1	0	0	1	0	0
4	1	0	1	0	0	0
5	1	0	1	0	1	0
6	1	0	0	0	0	1
7	1	0	0	1	0	1
8	1	0	1	0	0	1

6의 이친수를 구하는데 4와 5의 이친수를 그린이유는 내가 찾은 공통점 때문에 그렇다.

그리고 끝이 0과 1로 끝나는 것을을 구분에서 0으로 끝나는 것들 먼저 1로 끝나는 것들 먼저 그려보았다.

일단 먼저 0으로 끝나는 것들을 보자면

1	1	0	0	0	0	0
2	1	0	0	0	1	0
3	1	0	0	1	0	0
4	1	0	1	0	0	0
5	1	0	1	0	1	0

색칠한 부분을 보면 5의 이친수들이다. 소름 돋았다.

그럼 1로 끝나는 것들을 볼까?

6	1	0	0	0	0	1
7	1	0	0	1	0	1
8	1	0	1	0	0	1

이것또한 색칠한 부분을 보면 4의 이친수들인다. 역시나 소름돋았다.

그럼 이제 점화식을 구하고 코딩하면 되겠다.

힘든 과정이었다.

자리수멸 이친수의 값을 배열에 저장하고 입력받은 숫자 N 가질 까지 이친수의 자릿수를 저장한다음 호출하면 된다.

이친수의 개수는 1자리는 그냥 기본값으로 배열에 저장하고 나머지 값들을 계산할 예정이다.

cnt[N] = cnt[N-1] + cnt[N-2]

점화식을 구했으니 이제 코딩을 해보자.

문제를 풀때 90자리까지가면 int 의 MAX 크기를 초과한다. 타입은 int를 쓰지말고 long을 쓰자

소스

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

import java.util.Scanner;   public class E_2193 {     public static void main(String[] args) {         // TODO Auto-generated method stub         Scanner sc = new Scanner(System.in);         int num = sc.nextInt();         long cnt[] = new long[num+1];         cnt[0] = 0;         cnt[1] = 1;         for(int i=2; i <= num; i++) {             cnt[i] = cnt[i-1] + cnt[i-2];         }         System.out.println(cnt[num]);     }   } Colored by Color Scripter

cs