[JAVA] 백준 9184 신나는 함수 실행

9184번: 신나는 함수 실행 (acmicpc.net)

9184번: 신나는 함수 실행

 

재귀 함수 w(a,b,c)

 

- a,b,c가 주어졌을 때 w(a,b,c)를 출력하는 프로그램 

 

 

풀이 과정 

 

 

동적 프로그램(DP, 동적 계획법)

 

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드) (tistory.com)

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)

 

- "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법 

- 동적 프로그래밍은 분할 정복이 동일하다고 생각할 수 있지만 해를 구하기 위해 쪼갠 "부분 문제"의 특성이 다르다 

- "큰 문제"를 찾기 위해 여러 "부분 문제"를 반드시 풀어야 하고 "부분 문제"는 반드시 중복해서 나타남

 

- 중복되는 부분 문제(Overlapping Subproblem)는 분할 정복과 동적 프로그래밍의 가장 큰 차이 

- 분할 정복은 "큰 문제"가 "유니크한 부분 문제"로 나뉘지만 동적 프로그래밍은 "부분 문제"가 반복적으로 등장 

 

- "큰 문제"의 해를 찾기 위한 연산과 "부분 문제"의 해를 찾기 위한 연산이 동일해야 하며 "부분 문제"의 해를 조합해 "큰 문제"의 해를 찾을 수 있는 구조를 최적 부문 구조(Optimal Substructure)라고 함

- "큰 문제"의 해는 "부분 문제"의 조합으로 찾을 수 있으며 문제의 해는 동일한 연산으로 수행되어야 함 

 

- 동적 프로그래밍에선 중복된 계산을 피하고자 이전에 구한 "부분 문제"의 해를 메모리에 저장해두며 이를 메모이제이션(Memoization)이라고 함 

 

 

- 메모이제이션을 활용한 재귀로 풀이 

- memo[][][]에 저장한 값이 0이 아니라면 이미 계산된 문제 이므로 그 값을 리턴 

- 조건에 맞춰 연사을 수행한 후 , 그 결과값을 memo[][][]에 저장 후 리턴 

 

 

정답 

 

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

public class Main {
    static int memo[][][] = new int[21][21][21];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringBuilder sb = new StringBuilder();
        
        while(true)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            
            if(a==-1&&b==-1&&c==-1)
                break;
            
            sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a ,b ,c)).append('\n');
        }
        
        
        System.out.println(sb);
    }
    
    static int w(int a,int b,int c)
    {
        if(check(a,b,c)&& memo[a][b][c] !=0)
        {
            return memo[a][b][c];
        }
        
        if(a<=0||b<=0||c<=0)
        { 
             return 1;
        }
        
        if(a>20||b>20||c>20)
        {
            return memo[20][20][20] = w(20,20,20);
        }
        
        if(a<b&&b<c)
        {
            return memo[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
        }
        
        return memo[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);
 
    }
    
    //범위 조건
    static boolean check(int a,int b,int c)
    {
        return 0<=a && a<=20 && 0<=b && b<=20&& 0<=c && c<=20;
    }
}