백준 - 9095번 - 1, 2, 3 더하기

9095번

1. 메모라이징 활용해서 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	// Integer로 선언하면 null값 사용가능
	static Integer[] dp;

	static int recur(int N) {
		if (dp[N] == null) {
			dp[N] = recur(N-1) + recur(N-2) + recur(N-3);
		}
		return dp[N];

	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		dp = new Integer[11+1];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;

		for (int i = 0; i<N; i++) {
			int A = Integer.parseInt(bf.readLine());

			System.out.println(recur(A));
		}
	}
}

2. 반복문 + 배열로 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());

		Integer[] dp;
		dp = new Integer[11+1];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for (int i = 0; i<12; i++) {
			if (dp[i] == null) {
				dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
			}
		}
		for (int i = 0; i<N; i++) {
			int A = Integer.parseInt(bf.readLine());

			System.out.println(dp[A]);
		}
	}
}

풀이

두가지 풀이의 가장큰 차이점은 1번은 배열을 필요한 만큼만 만들어서 풀수 있고, 2번은 전부 만들어야하는 것이다. 지금은 N이 11이여서 오히려 2번이 성능이 좋다. 하지만 N이 커질수록 1번의 효율은 상황에 따라 높아질것이다.

성능비교

위 -> 1. 메모라이징 활용해서 풀기
아래 -> 2 반복문 + 배열로 풀기