[백준/2193/Java] 이친수

 

 

문제링크

www.acmicpc.net/problem/2193

2193번: 이친수

 

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

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

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다.

 

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

 

풀이

이친수는 제가 아는 풀이법으로 2가지가 존재합니다.

 

일단 0이 아닌 숫자로 시작하기 때문에 항상 맨 앞에 있는 숫자는 1입니다.

이건 2가지 풀이법 모두 공통된 부분입니다.

 

그리고 N이 최대가 90인데 D 배열을 int로 하면 음수가 됩니다.

즉, int 범위를 초과하는 것입니다.

수학을 잘 하시는 분들은 int 범위를 넘는 것을 예측하시겠지만 저는 일단 90을 넣어서 값을 확인해봅니다.

따라서, D배열은 long 형으로 선언해서 사용해야 합니다.

 

0자리수는 0개, 1자리수는 1개만 존재하므로 초기화를 그렇게 하셔야 합니다.

 

1번째 풀이법 (2차원 배열)

 

위 그림을 보시면 3자리 수에서 4자리 수가 될 때 추가되는 숫자를 빨간 색으로 표시하였습니다.

 

점화식 규칙을 찾아보기 위하여 2번째 규칙을 보겠습니다.

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

 

2번째 규칙을 보면 11이 불가능하므로 00, 01, 10이 가능합니다.

3자리 수에서 마지막으로 끝나는 숫자 기준으로 보겠습니다.

D배열을 2차원 배열로 생각하면 이렇게 표현할 수 있습니다.

A. 0으로 시작하는 경우 : 00, 01

  - D[4][0] = D[3][0] + D[3][1]

B. 1로 시작하는 경우 : 10

  - D[4][1] = D[3][0]

 

1번째 풀이법 소스

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main
{
	static int n;
	static long D[][] = new long[91][2];
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		D[1][0] = 0;
		D[1][1] = 1;
		
		for (int i = 2; i <= n; i++)
		{
			D[i][0] = D[i-1][0] + D[i-1][1];	// 0으로 시작
			D[i][1] = D[i-1][0];			// 1로 시작
		}
		
		System.out.println(D[n][0] + D[n][1]);
	}
}

 

 

2번째 풀이법 (1차원 배열)

점화식을 찾을 때 N번째에서 N-1, N-2 등 역순으로 규칙을 찾아보겠습니다.

4자리 수에서 그 이전 수와 비교해보면 위 그림과 같이 됩니다.

항상 1로 시작하기 때문에 3자리 수에서 맨 앞에 1를 제외하고 보면 겹치는 부분을 빨간색으로 표시했습니다.

A. 4자리 수 중 2개는 3자리 수에서 존재하는 모든 수와 개수가 동일합니다.

B. 4자리 수 중 1개는 2자리 수에서 존재하는 모든 수와 개수가 동일합니다.

  

5자리 수도 보겠습니다.

A. 5자리 수 중 3개는 4자리 수에서 존재하는 모든 수와 개수가 동일합니다.

B. 5자리 수 중 2개는 3자리 수에서 존재하는 모든 수와 개수가 동일합니다.

따라서, 점화식은 D[N] = D[N-1]+ D[N-2]가 됩니다.

 

2번째 풀이법 소스

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main
{
	static int n;
	static long D[] = new long[91];
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		D[0] = 0;
		D[1] = 1;
		
		for (int i = 2; i <= n; i++)
		{
			D[i] = D[i-1] + D[i-2];
		}
		
		System.out.println(D[n]);
	}
}