이친수 구하기 - 동적계획법

동적계획법

동적 계획이란 큰 문제를 작은 문제로 나눠서 작은 문제들을 해결해 최종적으로 큰 문제를 해결하는 방법이다.

 

동적 계획법 핵심 이론

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.

2. 작은 문제들이 반복되서 나타나야하고, 이 작은 문제들의 결과가 항상 같아야 한다.

3. 작은 문제들은 한 번만 계산해서 저장해두고, 추후에 계산해둔 작은 문제들을 재사용 해야한다. - 메모제이션 원리

4. 톱-다운 방식, 바텀-업 방식으로 구현할 수 있다.

 

톱 다운 방식

위에서 아래로 문제를 계산하는 방식

 

바텀 업 방식

아래에서 위로 문제를 계산하는 방식

예시

arr[0] = 0;
arr[1] = 1;

for (int i = 2; i <= 10; i++) {
	arr[i] = arr[i - 1] + arr[i - 2];
}

이런식으로 바텀의 값들을 사용하여 업의 값을 구하는 방식을 바텀 업 방식이라고 한다.

 

문제 풀이

이친수 구하기

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

2193번: 이친수

동적 계획법을 이용해서 풀 수 있는 문제이다.

동적 계획법은 점화식을 구하는 게 핵심이다.

 

끝 자리가 0으로 끝나는 이친수,

끝 자리가 1로 끝나는 이친수 

이렇게 두 개로 나눠서

(자리수가 5자리라는 가정)

0으로 끝나는 5자리 이친수 + 1로 끝나는 5자리 이친수

이렇게 결과를 도출한다.

 

0으로 끝나는 5자리 이친수 = 0으로 끝나는 4자리 이친수 + 1로 끝나는 4자리 이친수

1로 끝나는 5자리 이친수 = 0으로 끝나는 4자리 이친수

이 개념을 이용해 점화식을 세워서 사용했다.

 

내 풀이

import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		long[][] arr = new long[num + 1][2]; // 0으로 끝나는거 1로 끝나는거
		
		arr[1][0] = 0; // 0으로 끝나는 1자리 이친수 개수. 0으로 시작하면 안되니까 0 대입
		arr[1][1] = 1; // 1로 끝나는 1자리 이친수 개수
		
		for (int i = 2; i <= num; i++) {
		    arr[i][0] = arr[i - 1][0] + arr[i - 1][1]; 
		    arr[i][1] = arr[i - 1][0]; // 1다음에 1이 오면 안되니까
		}
		
		long result = arr[num][1] + arr[num][0];
		bw.write(String.valueOf(result));
		br.close();
		bw.flush();
		bw.close();
	}
}

주의할 점 

arr의 자료형을 int가 아니라 long으로 해야한다.

int로 하면 최대 자리수가 90개 일때 만들수 있는 이친수 개수가 1000000000개가 넘어서 담지 못한다.

 

참고 : do it 알고리즘 코딩테스트 자바편