백준 : 1 2 3 더하기 (점화식)

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

9095번: 1, 2, 3 더하기

나는 처음에 재귀를 통해서 문제를 풀었다. 

재귀로 풀게된 이유는 해당 입력값을 각각 1, 2, 3으로 한번씩 빼고, 거기서 나온 값을 또 1, 2, 3을 뺴는 식으로 반복한 뒤, 마지막으로  0이 나온것들의 카운트를 세면 된다고 생각했기 때문이다.

 

4 - 1 =3 여기서 또 1 ,2, 3 각각 빼기 반복

4 - 2 =2 여기서 또 1 ,2, 3 각각 빼기 반복

4 - 3 =1 여기서 또 1 ,2, 3 각각 빼기 반복

그러면 DFS 모양과 비슷한 모습을 찾을 수 있었다. 

 

DFS는 스택함수를 기초로 재귀함수를 사용하기 떄문이다. 물론 문제는 맞았으나, 다른 사람들의 풀이를 보니 점화식으로 사용한 경우가 무척 많이있었다. 그리하여 점화식을 구하게된 방법과 구현하는 방법도 연습할겸 시도해보았다.

 

재귀사용

package com.controller;

import java.util.Scanner;

public class Main {
	
	public static int count =0;
	public static int[] baseArr = {1,2,3};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[] numArr = new int[num];
		for(int i=0; i<num; i++) {
			numArr[i] = sc.nextInt();
		}
		
		for(int i=0; i<num; i++) {
			mathCal(numArr[i]);
			System.out.println(count);
			count =0;
		}
	}
	
	public static void mathCal(int in) {
		for(int i=0; i<3; i++) {
			int tmp = in - baseArr[i];

			if(tmp == 0) { //종료조건
				count++;
				return;
			}
			
			if(tmp > 0) {
				mathCal(tmp); //재귀
			}
		}
		return;
	}
}

 

점화식 사용

package com.controller;

import java.util.Scanner;

public class Main {
	
	public static int count =0;
	public static int[] baseArr = {1,2,3};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt(); //3
		
		int[] numArr = new int[num];
		for(int i=0; i<num; i++) {
			numArr[i] = sc.nextInt(); //[4,7,10]
		}
		
		int[] dp = new int[11];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		//dp[4] = 7 -> 1+2+3 = dp[3] + dp[2] +dp[1]
		
		for(int i=0; i<num; i++) {
			for(int j=4; j <=numArr[i]; j++) {
				dp[j] = dp[j-3] + dp[j-2] + dp[j-1]; //점화식
			}
		}
		for(int i=0; i<num; i++) {
			System.out.println(dp[numArr[i]]);	
		}
	}
}

재귀사용