[백준 2193번] 이친수 (자바)

백준알고리즘 2193번 : 이친수 (Solved.ac 난이도 Silver3)

 

 

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

2193번: 이친수

 

 

규칙을 찾고나면 어렵지 않게 풀 수 있는 문제같다.

그리고 규칙을 찾는 방법은 작은 경우에서부터 하나씩 크기를 늘리면서 앞전 경우와 연결되는 연속성을 발견하는 것이다.

예를 들어 3자리 숫자일때와 4자리 숫자일때를통ㅇ해 규칙을 찾아보자.

3자리 숫자일때는 100, 101로 총 2가지 경우의 수가 있다.

4자리 숫자일때는 1000, 1010, 1001로 총 가지 경우의 수가 있는데,
이 경우의 수는

' 0으로 끝나는 경우'와  '1로 끝나는 경우'로 나뉜다.
그리고 0으로 끝나는 경우는 n-1자리 숫자일때의 경우의 수와 정확히 일치한다.
또한 1로 끝나는 경우의 수는 n-1자리 숫자의 경우의 수 중, 마지막이 0으로 끝나는 경우의 수와 일치한다.

죽, Sn = Sn-1 + An-1로 표현할 수 있을 것이다.
Sn (n자리 숫자의 경우의 수)
An-1 (n-1자리 숫자가 0으로 끝나는 경우의 수)

그런데 이렇게 나누다보면,

S1과 S2가 각각 1인 피보나치 수열이라는 것을 알수있다.

따라서 그냥 피보나치 수열을 적용하여 풀어주었다.

 

 

풀이 과정

---

1. 문제에서 받을수 있는 값의 최대길이 만큼 배열을 생성한다. -length 91
2. 배열 arr의 초기값을 넣어준다. arr[1]=arr[2]=1
3. 받은 숫자 N만큼 for문을 돌면서 배열의 값을 채워나간 뒤 출력한다.

 

 

 

▽ 정답 소스 보기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { // [Silver3] 2193번 : 이친수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        long [] arr =new long [91];
        arr[1]=1;
        arr[2]=1;
        for (int i = 3; i <= num; i++) {
                arr[i]=arr[i-1]+arr[i-2];

        }
        System.out.println(arr[num]);
    }
}