JAVA 백준 알고리즘 문제풀이/동적 계획법

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

Xerath(제라스) 2021. 12. 4. 18:54
728x90
반응형

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

 

9184번: 신나는 함수 실행

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

www.acmicpc.net

 

1. 문제

 

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 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=15, b=15, c=15)

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

2. 입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

3. 출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

4. 풀이

이전 문제와 같이 메모이제이션을 이용하여 계산한 값을 미리 저장해둔 후, 그 값을 필요로 할 때 계산 대신 memo된 값을 가져다 사용하였다. 배열의 인덱스로 음수를 가져오거나 20보다 큰 값을 가져오지 않기 위해서 미리 break을 하거나 range함수를 구현하여 가능한 범위만을 설정하여 배열에서 발생할 수 있는 에러를 미리 방지해두었다.

5. 소스코드

import java.io.*;
import java.util.*;
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));
        
        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));
            
        }
    }

    public static int w(int a, int b, int c){
        
        if(range(a,b,c)&&memo[a][b][c] != 0) return memo[a][b][c];
        else{
            if(a<=0 || b<=0 || c<=0) return 1;

            else if(a>20 || b>20 || c>20){
                return memo[20][20][20] = w(20, 20, 20);
            }

            else 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);
            }
            else{
                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);
            }
        }
    }

    public static boolean range(int a, int b, int c){
        return 0<=a && a<=20 && 0<=b && b<=20 && 0<=c && c<=20;
    }
}

6. 배운 것

 

이 문제에서 가장 나이스한 부분은 range 설정이었다. return문에 바로 조건문을 넣어두고 boolean 값을 리턴하는 것이 문제 풀이를 하며 배운 가장 중요한 부분 중 하나였다. 저런 식으로 작성하는 스킬을 가져가는 기회가 되었다.

 

또한, 문제를 단순히 조건문을 긁어올 것이 아니라 조건에 따라 범위를 설정할 수도 있고 제한을 두어 메모리를 아낄 수 있다는 점을 배웠다. a,b,c 중 하나라도 20보다 클 때는 무조건 w(20, 20, 20)인 점, 하나라도 0이하일 때는 무조건 1인 점 등을 고려하여 배열 크기를 [21][21][21]로 설정해 줄 수 있다. 조건이 곧 메모리 절약과 시간 단축에 도움이 될 수 있단 것을 간과하면 안되겠다.

728x90
반응형