[알고리즘][Java] 백준(BOJ) 2193 이친수_자바

 

DP

2193 이친수    https://www.acmicpc.net/problem/2193

2193번: 이친수

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n을 Scanner로 입력받는다.
• 1번 규칙에 의해 n = 1 일 때는 1만 가능하다.
• n = 2 일 때는 1 뒤에 0만 올 수 있다.
• 2번 규칙에 의해 N자리에 0이 올 수 있는 경우는 앞의 숫자가 0 또는 1일 때이고, 1이 올 수 있는 경우는 앞의 숫자가 0일 때만 가능하다.
• 위의 규칙을 이용해서 개수를 세면 된다.
• dp에 초기값이 0인 2차원 배열을 저장한다.
  • dp [n+1][2]의 형태이다.
• 위의 규칙대로 for문을 돌면서 개수를 저장한다.

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		
		long[][] dp = new long[n+1][2];
		dp[1][1] = 1;
		
		for (int i=2; i<=n; i++) {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0];
		}
		
		System.out.println(dp[n][0] + dp[n][1]);

	}

}

 

 

 

 

 

 

 

비슷한 풀이의 난이도 있는 문제 : https://www.acmicpc.net/problem/11057

11057번: 오르막 수