[백준] 2193번 이친수 (DP_Java)

DP는 연습할 수록 쉬워지고,

안할 수록 말도 안되게 어려워지는 문제인 것 같다.

 

코딩테스트에 꾸준히 나오고 있으니까

열심히 해야겠다.

 

---

문제

 

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

2193번: 이친수

 

 

---

설계

 

알고리즘 설계 [접근 방법] : DP

DP 문제 중에서도 점화식의 규칙을 찾아야 하는 문제다. 이게 무슨 문제야..하고 1부터 7자리까지 손으로 세다가 점화식을 발견했다.

 

1부터 3까지는 초기화로 설정값을 넣어주고, 4부터 n까지 규칙을 적용하면 된다. 이 문제를 자세히 살펴보면 자리수라는 힌트가 나온다. 1자리 수는 '1'만 사용 가능하므로 값이 1이 된다. 2자리 수는 '10'만 가능하므로 역시 정답은 1이다. 3은 '100', '101'이 가능하므로 정답은 2다.

 

만약 5자리수라면 1번과 2번 자리는 1과 0만 들어갈 수 있다. 그럼 3, 4, 5번 째 자리수에 무슨 숫자를 넣느냐에 따라 경우의 수가 나오는 것이다. 

여기서 확인할 점은 5자리 중 처음 2자리는 고정이고 나머지 자리수는 이미 설정해놓은 값을 활용하면 된다는 것이다. 그런데 여기서 주의할 점은 5자리 이친수라고 하면 10 000도 포함되어야 한다.

그러므로 5자리 이친수의 경우의 수는 1(1자리 활용) + 1(2자리 활용) + 2(3자리 활용) + 1 (10000의 경우) 가 된다.

 

주의할 점

여기서 주의할 점은 n의 최대값이 90이다. 90자리수는 10억이 훌쩍 넘는다. 그러므로 정답을 int가 아닌 long으로 해주어야 한다.

 

풀이 과정

1.

자리수 n을 입력받는다.

만약 n이 1이나 2라면, 정답 1을 출력하고 return한다. 만약 n이 3이라면, 정답 2를 출력하고 return한다.

 

2.

점화식을 적용할 2차원 배열 dp를 생성한다.

0행은 현재 자리수에 이친수가 몇개 생성할 수 있는 지를 저장할 행이고, 1행은 현재 자리수까지의 누적합을 저장한다.

 

1부터 3까지 최초 설정값을 저장한다.

 

3.

4부터 n+1까지 반복문을 진행한다

dp[0][i]의 값은 1부터 i의 이친수의 경우의 수를 더한 값에 1를 더해야 한다. 그러므로 점화식은 dp[0][i] = dp[1][i-2]+1가 된다.

dp[1][i]의 값은 누적합을 저장해야 하므로, 여태까지 저장한 누적합 dp[1][i-1]에 dp[0][i]의 값을 더하면 된다. 식으로 보면 dp[1][i] = dp[1][i-1]+dp[0][i]가 되는 것이다.

 

4.

반복문이 종료되면, dp[0][n]의 값을 출력하면 된다.

 

 

---

코드

 

import java.util.Arrays;
import java.util.Scanner;

public class Test_2193_이친수 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		//1, 2, 3일 경우
		if(n==1 || n==2) {
			System.out.println(1);
			return;
		} else if(n==3) {
			System.out.println(2);
			return;
		}
		
		//dp 배열 생성
		long[][] dp = new long[2][n+1];
		dp[0][1] = 1;   dp[1][1] = 1;
		dp[0][2] = 1;   dp[1][2] = 2;
		dp[0][3] = 2;   dp[1][3] = 4;   
		
		//계산
		//0행 : 현재 자리수가 가질 수 있는 이친수의 개수
		//1행 : 1의 자리수부터 현재 자리수까지 가질 수 있는 이친수 개수의 누적 합
		for(int i=4; i<n+1; i++) {
			dp[0][i] = dp[1][i-2]+1;
			dp[1][i] = dp[1][i-1]+dp[0][i];
		}
		
		//출력
		System.out.println(dp[0][n]);
	}
}

 

 

(❁´◡`❁)

끝!