200918 금 [BOJ] 11726, 11727, 9095

💡 DP의 문제 풀이 방법

1. 문제에서 구하려고 하는 답을 문장으로 나타낸다.
2. 그 문장에 나와있는 변수의 갯수만큼 메모하는 캐시 배열을 만든다.
3. Top-down 인 경우에는 재귀호출의 인자의 갯수가 된다.(?)
4. 마지막으로, 문제를 작은 문제로 나누고 수식(점화식)을 이용하여 문제를 표현한다.

(출처 : https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming)

BOJ 11726

Bottom-up 방식으로 푼건데 런타임 에러 발생.

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

public class Main {
	
	public static int f[];
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();
    	
    	f = new int[N+1];
    	
    	System.out.println(fibonacci(N));
    	
    }

    //Bottom-Up 방식
	private static int fibonacci(int N) {
		f[1] = 1;
		f[2] = 2;
		for(int i=3;i<=N;i++) {
			f[i] = f[i-1] + f[i-2];
			f[i] = f[i]%10007;
		}
		return f[N];
	}
}

Top-down으로 푼 방식도 시간 초과...?!😨

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

public class Main {
	
	public static int f[];
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();
    	
    	f = new int[N+1];
    	
    	System.out.println(fibonacci(N));
    	
    }

    //top-down
	private static int fibonacci(int N) {
		if (N==1) {
			f[N] = 1;
			return f[N];
		} else if (N==2) {
			f[N] = 2;
			return f[N];
		} else {
			f[N] = fibonacci(N-1) + fibonacci(N-2);
			return f[N];
		}
	}
}

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

public class Main {
	
	public static int f[];
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int N = Integer.parseInt(br.readLine());
    	br.close();
    	
    	f = new int[N+1];
    	
    	System.out.println(fibonacci(N));
    	
    }

    //top-down
	private static int fibonacci(int N) {
		if (N==1 || N==2) {
			f[N] = N;
			return f[N];
		} else if (f[N]>0) {
			return f[N];
		} else {
			f[N] = fibonacci(N-1) + fibonacci(N-2);
			return f[N] % 10007;
		}
	}
}

성공🌝 캐시 배열 에 입력한 값을 전혀 사용하지 않고 있었다.. 그러니 계속 계산을 반복하면서 런타임 에러가 뜬 것이 아닌가.. 생각된다.
(Bottom-up 방식이 런타임 에러가 뜨는 것은 왜 그러는지 모르겠다..)

---

BOJ 11727

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		br.close();
		
		int[] dp = new int[1001];
		
		dp[1] = 1;
		dp[2] = 3;
		
		for(int i=3;i<=n;i++) {
			dp[i] = (dp[i-1] + dp[i-2]*2) % 10007;
		}
		System.out.println(dp[n]);
	}
}

Bottom-up으로 풀었다.
2X2 타일을 추가한 것이 f[n-2]의 경우가 하나 더 추가된 거라는 해설이 많아서 그렇게 풀긴했는데.. 뭔가 알듯 말듯 와닿지 않는다.

계속 런타임 에러😡가 나서 구글링을 좀 해보니, 배열 선언 에서 문제가 있었다. 배열의 크기를 내가 계속 했던대로 n+1로 하면 n=1일 때 밑에서 선언한 dp[2]의 값에서 오류가 생길 것이다.
따라서 문제에서 주어진 n의 범위 +1 인 1001로 배열의 크기를 선언해주고 시작하면 성공!

---

BOJ 9095

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());	
		
		dp = new int[11];
		
		for(int i=0;i<T;i++) {
			int n = Integer.parseInt(br.readLine());
			int answer = calc(n);
			bw.write(String.valueOf(answer + "\n"));
		}
		br.close();
		bw.flush();
		bw.close();
	}

	private static int[] dp;
	
	private static int calc(int n) {
		if(dp[n] > 0)
			return dp[n];
		
		if (n == 1) {
			dp[1] = 1;
			return dp[n];
		}
		if (n == 2) {
			dp[2] = 2;
			return dp[n];
		}
		if (n == 3) {
			dp[3] = 4;
			return dp[n];
		}
		dp[n] = calc(n-1) + calc(n-2) + calc(n-3);
			
		return dp[n];
	}
}

n-3의 case들에서 +1이나 +2로 인해 추가될 case들은 모두 n-1과 n-2의 경우에서 처리되었으므로, 중복을 없애기 위해 결국 +3의 case들만 더해지면 된다. 즉, n-3의 경우의 수가 그대로 더해지면 된다.
n-2의 case도 마찬가지. +1로 인해 추가될 case들은 모두 n-1에서 처리되었다.
n-1의 모든 case에 +1을 한 것뿐이기 때문에, 결국 경우의 수는 n-1의 것이 그대로 더해지면 된다.