백준 9184 신나는 함수 실행 - JAVA

9184 문제 링크

---

 

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

 

문제 설명

---

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while(true) {
            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(answer(a,b,c)); sb.append("\n");         }
        bw.write(sb.toString());
        bw.flush();
    }
    
    private static int answer(int a, int b, int c) {
        if(isValid(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] = answer(20, 20, 20);
        }
        else if(a < b && b < c) {
            return memo[a][b][c]  = answer(a, b, c-1) + answer(a, b-1, c-1) - answer(a, b-1, c);
        } else {
            return memo[a][b][c]  = answer(a-1, b, c) + answer(a-1, b-1, c) + answer(a-1, b, c-1) - answer(a-1, b-1, c-1);
        }
    }
    
    private static boolean isValid(int a, int b, int c) {
        if(0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20) {
            return true;
        } else {
            return false;
        }
    }
}

 

알고리즘 설명

---

동적 계획법 즉, 다이나믹 프로그래밍이란 정해진 규칙이나 공식은 없지만, 문제를 해결하기 위한 효율적인 방법 중 하나로,
문제를 여러 개의 하위 문제로 나누어 그 해결 결과를 저장하고 재사용하는 방식입니다.
이 방식은 반복적인 계산을 피하고, 중복되는 부분 문제를 해결할 때 시간 복잡도를 줄이는 데 유리합니다.
 
해당 문제에서는 a, b, c의 수가 커질수록 코드의 실행 시간이 걷잡을 수 없이 커지기 때문에, 미리 계산된 값을 저장하는 것이 중요합니다.
이러한 해결방식을 메모이제이션(Memoization)이라고 합니다.
풀이 함수(answer 함수)의 재귀호출 시, 한 번 계산된 값은 다시 계산하지 않고, 저장된 결과를 이용하는 것이 핵심입니다.

 

코드 해석

---

main함수와, answer함수에 사용될 memo라는 3차원 배열을 전역으로 선언합니다.
a, b, c의 값이 최대 20까지 이용되기 때문에, 0을 제외한 1~20까지 숫자를 담을 크기를 [21][21][21]로 선언합니다.
 
계산된 값을 재사용하기 위해, 입력된 값을 memo라는 3차원 배열에 저장해야하는데,
memo배열의 값은 최대 21 이기때문에, isValid라는 유효성 검사를 수행시켜, 저장될 값이 배열 크기를 초과하지 않도록 합니다.
(memo배열의 ArrayIndexOutofBounds를 방지)
 
입력된 a, b, c중 하나라도 0 이하인 경우에는 1을 리턴,
하나라도 20이상인 경우에는 a, b, c의 값을 20으로 변경하고, 호출한 값을 memo[20][20][20]에 담습니다.
a < b && b < c인 경우에는, 주어진 실행문을 memo[a][b][c]에 담습니다.
위의 세가지 조건을 제외한 경우, 주어진 실행문을 memo[a][b][c]에 담습니다.
 
문제를 풀어보셨을 때, 계산한 값을 저장할 배열을 생각하셨다면, 크게 어렵지 않은 문제였다고 생각합니다.
개인적으로, 동적 계획법 관련 문제들은 많이 풀어보고 익숙해지는게 중요한것 같습니다.
 
- 참고 -

• ArrayIndexOutofBounds : 배열 인덱스 초과 예외