[백준] 9184번 신나는 함수 실행 JAVA (자바) 풀이

문제 9184번 (DP)

 :  재귀함수 w(a, b, c)가 있다

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

 

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

 

 

 otherwise w(2a-2, 2b, c) 출력력

 

 

[입력]

 :  입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다

    (입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다)

 

 

[출력]

 

 :   w(a, b, c)를 출력

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. 문제 코드대로 작성하기

• 조건1) if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:    1
  • ||연산에 0과 같거나 작으면 1출력
    
    
• 조건2) if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:    w(20, 20, 20)
  • ||연산에 20보다 크면 w(20, 20, 20) 재귀 호출
    
    
• 조건3) if a < b and b < c, then w(a, b, c) returns:    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
  • &&연산에 a < b 거나 b < c 이면  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) 재귀 호출
  • 여러번 재귀일 경우는 dp를 활용해 dp[a][b][c] 출력
  • 조건에는 없지만 0이 아니고 20이 넘지 않아야 해당 조건문이 실행
    
    
• 조건 4) otherwise it returns:    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
  • 여러번 재귀일 경우 마찬가지로 dp 활용해 dp[a][b][c] 출력
  • 조건에는 없지만 0이 아니고 20이 넘지 않아야 해당 조건문이 실행

 

 2. dp 이용 시 규칙

• 위에서 말했던 숨겨진 조건 중 dp를 활용할 경우에는 0~20 안에서만 움직이므로
  크기를 21로 지정한다
  
  
• dp안에 값이 있는지 확인하면서 움직여야 여러번 재귀 호출을 하지 않는다
  이미 이전에 계산된 값이라면 재귀없이 바로 호출하기

 

 [코드]

import java.io.*;
import java.util.*;
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));
        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;
            }
            System.out.println("w("+a+", "+b+", "+c+") = "+w(a,b,c));
            
        }
    }
    
    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];
    }
}

 

 

 [해설]
     

 :  static int dp[][][] = new int[21][21][21];  dp크기 21로 지정
   

 :  while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int a = Integer.parseInt(st.nextToken());  a 입력
            int b = Integer.parseInt(st.nextToken());  b 입력
            int c = Integer.parseInt(st.nextToken());  c 입력
            
            if(a==-1 && b==-1 && c==-1){  모두 -1 이라면 반복문 종료
                break;
            }
            System.out.println("w("+a+", "+b+", "+c+") = "+w(a,b,c));  결과 출력
    }
    
    
 :  static int w(int a, int b, int c){  w 재귀
        if(a<=0 || b<=0 || c<=0){  조건 1 실행
            return 1;
        }
        
        if(a>20 || b>20 || c>20){  조건 2 실행
            return w(20, 20, 20);
        }
        
        if(dp[a][b][c]!=0){  무한한 재귀 호출을 막기위해 미리 계산한 값 있음 바로 출력
            return dp[a][b][c];
        }
        if(a<b && b<c){  조건 3 실행
            dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        else  조건 4 실행
            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 출력
    }

 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *