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

문제 2193번 (DP)

 : 0과 1로만 이루어진 수를 이진수

 

  이친수 특성

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

   예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수 (하지만 0010101이나 101101 이친수가 아니다)

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

 

 

[입력]

 :  첫째 줄에 N

 

 

[출력]

 

 :   첫째 줄에 N자리 이친수의 개수를 출력

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1.점진적 규칙 찾기

• dp[1]의 경우
  0과 1 중 1만 올 수 있다
  
  
• dp[2]의 경우
  앞에는 무조건 1 뒤에는 0만 올 수 있다
  dp[1] + 0 = 1가지
  
  
• dp[3]의 경우
  앞에는 무조건 1이 오고 연속된 1은 안되니까 그다음 숫자는 0, 그다음 숫자는 0 또는 1 이 된다
  dp[2] + 0 or 1 = 2가지 = dp[0] + dp[1]
  
  
• dp[4]의 경우
  앞에는 무조건 1오고 연속된 숫자는 안되니까 그다음 숫자는 0, 그다음 숫자는 0 또는 1 마지막 숫자도 0 또는 1
  1000 / 1001 / 1010 = 3가지 = dp[2] + dp[3]
  
  
• 간단히 설명하자면
  맨 뒷자리를 기준으로 하나만 붙일 수도 있고 0/1 둘 다 붙일 수도 있다
  그건 앞자리 수에 따라서 달라지기 때문이다
  앞자리 점화식은 계산해보면 d[i-1] + d[i-2]와 같으므로 해당 식을 이용한다

 

2. 인덱스 예외처리 발생

• N이 1부터 입력받기 때문에 당연히 dp[1]부터 dp[2]까지만
  
  
• 2가지만 초기화한 이유
  dp 점화식이 2가지 식이 필요하다
  dp[i-1] / dp[i-2]이므로 2개의 식을 초기화 했다
  
  
• 그럼에도 에러가 나는 이유
  인덱스가 1 즉 N=1일 경우 dp[2]는 현재범위에서 벗어나기 때문에 식 자체를 생성할 수 없다
  해결 방법으로는 if문 조건에 N>=2로 달아주거나 애초에 dp[0]부터 dp[1]까지 초기화 해줘도 된다
  또한 처음 dp배열을 new int[N+1]가 아닌 new int[91] 이라고 해도 에러가 나지 않는다
  
  

3. 그래도 틀렸다면 자료형 바꾸기

• int형에서 long으로 바꾸니 알맞게 돌아간다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long dp[] = new long[N+1];
        
        dp[1]=1;

        if(N>=2)dp[2]=1;
        
        for(int i=3; i<=N; i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        
        System.out.println(dp[N]);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[N+1];  dp 배열 
        
 :  dp[1]=1;  1일 경우 1가지
    if(N>=2)dp[2]=1; 10의 자리일 경우 1가지 (인덱스 범위 잡아주기)
        
 :  for(int i=3; i<=N; i++){  이전 인덱스와 그보다 더 이전 인덱스 더해주기
            dp[i] = dp[i-1]+dp[i-2];
    }
        
 :  System.out.println(dp[N]);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *