[BAEKJOON] 9184 신나는 함수 실행

문제 요악

• 알고리즘 분류: 동적 계획법, 재귀호출
• 난이도: Silver2
• 문제 요약
  • 문제 있는 코드를 동적계획법으로 구현해라
• 사이트 주소: https://www.acmicpc.net/problem/9184

24416번: 알고리즘 수업 - 피보나치 수 1

 

문제 풀이

동적 계획법 관련 내용은 아래 사이트에 참조 하면된다.

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

 문제 접근 방법

 이번 문제는 위에 재귀호출 방식이 값 구하는 시간이 오래 걸려서 시간을 단축시키는 방법으로 변경해야 하는 작업이다.  그래서 최적화의 방법론인 동적계획법(dp) 방식으로 구현 해야 한다. 하지만 저위의 규칙이 몇가지가 더 있어서 재귀호출하면서 dp 로 구현해야 한다. 다른 동적계획법이랑 비교해서 보면 반복문으로 규칙만 몇개 작성만 해주면 되는데 이번 문제는 재귀호출은 필수라서 접근하기가 쉽지가 않은 문제이다.

  저 위에 코드는 그대로 두고 몇가지만 추가만 해주는 작업을 하면 된다. 그리고 값이 음수는 무조건 1이 나오고 정수로 20 이상이면 20, 20, 20 값이 랑 똑같기 때문에 dp 배열 사이즈를 각 20씩 하면 된다. 조건이 처리할 양이 많지 않아서 재귀호출하면서 dp로 구현해도 시간은 통과가 된다.

구현 방법

1. dp 배열 3차원으로 크기 20씩 선언을 한다.
2. 재귀 호출 코드를 추가를 해야 하는데, 기존 값이 있는 경우에는 리턴하고 없는 경우 재귀 호출한 값을 dp 배열에 값을 저장해서 리턴하면된다.

Code

Python

import sys
input = sys.stdin.readline

def w(a, b, c):
    if a<= 0 or b <= 0 or c <= 0: return 1
    
    if a > 20 or b > 20 or c> 20: return w(20, 20, 20)
    
    if dp[a][b][c] != 0: return dp[a][b][c]
    
    if a < b and b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b -1, c -1) - w(a, b-1, c)
    else: dp[a][b][c] = w(a- 1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    return dp[a][b][c]

dp = [[[0] * 21 for _ in range (21)] for _ in range(21)]
while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1: exit()
    print('w({}, {}, {}) = {}'.format(a, b, c, w(a, b, c)))

Java

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

public class Main {

	static int[][][] dp = new int[21][21][21];
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int a, b, c;
		while (true) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			if(a == -1 && b == -1 && c == -1) System.exit(0);
			System.out.printf("w(%d, %d, %d) = %d%n", a, b, c, w(a, b, c));
		}		
	}
	
	public static int w(int a, int b, int c) {
		if (a <= 0 || b <= 0 || c <= 0) return 1;
		
		if( a > 20 || b > 20 || c > 20) return w(20, 20, 20);
		
		if (dp[a][b][c] != 0) return dp[a][b][c];
		
		if (a < b && b < c) 
			dp[a][b][c] = w(a, b, c-1) + w(a, b -1, c -1) - w(a, b-1, c);
		else dp[a][b][c] = w(a- 1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
			
		return dp[a][b][c];
	}			
}