9184번: 신나는 함수 실행 - Kotlin, Java

9184번: 신나는 함수 실행

사진: Unsplash의Ozgu Ozden

 

 

문제

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

다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

---

 

 

나의 풀이

문제의 조건을 보면 엄청 막막하다는 생각이 듭니다. 하지만 이 문제에서는 dp를 사용해야 한다고 말해주고 조건이 그대로 나와있는 생각보다 친절한 문제입니다. 그렇기에 실버 2의 난이도를 가지고 있습니다.

 

사실 문제의 조건을 자세히 보면 첫 2개의 조건은 간단합니다. 

 

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

a, b, c 중 하나라도 0보다 작거나 같으면 1을 반환합니다. 이는 우리가 고려해야 할 a, b, c가 1 이상임을 의미합니다. 

 

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

a, b, c 중 하나라도 20보다 크면 w(20, 20, 20)을 반환합니다. 이는 우리가 고려해야 할 a, b, c가 20보다 크지 않다는 것을 의미합니다.

 

문제에서 주어진 a, b, c는 -50보다 크거나 같고 50보다 작거나 같다고 되어있습니다. 사실 이 조건 1, 2로 우리는 주어진 a, b, c의 범위를 1보다 크거나 같고 20보다 작거나 같다로 바꿀 수 있게 됩니다.

 

 

그럼 1 ~ 20의 값을 문제에서 주어진 나머지 조건 3, 4대로 구하면 됩니다.

 

Kotlin

fun main() = with(System.`in`.bufferedReader()) {

    val dp = Array(21) { Array(21) { IntArray(21) { 1 } } }
    dp[0][0][0] = 1

    for (a in 1..20) {
        for (b in 1..20) {
            for (c in 1..20) {
                if (a < b && b < c) {
                    dp[a][b][c] = dp[a][b][c - 1] + dp[a][b - 1][c - 1] - dp[a][b - 1][c]
                } else {
                    dp[a][b][c] = dp[a - 1][b][c] + dp[a - 1][b - 1][c] + dp[a - 1][b][c - 1] - dp[a - 1][b - 1][c - 1]
                }
            }
        }
    }

    while (true) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }

        if (a == -1 && b == -1 && c == -1) break

        if (a <= 0 || b <= 0 || c <= 0) {
            println("w($a, $b, $c) = 1")
        } else if (a > 20 || b > 20 || c > 20) {
            println("w($a, $b, $c) = ${dp[20][20][20]}")
        } else {
            println("w($a, $b, $c) = ${dp[a][b][c]}")
        }
    }
}

 

Java

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int[][][] dp = new int[21][21][21];

        for (int a = 0; a <= 20; a++) {
            for (int b = 0; b <= 20; b++) {
                for (int c = 0; c <= 20; c++) {
                    if (a == 0 || b == 0 || c == 0) {
                        dp[a][b][c] = 1;
                    } else if (a < b && b < c) {
                        dp[a][b][c] = dp[a][b][c - 1] + dp[a][b - 1][c - 1] - dp[a][b - 1][c];
                    } else {
                        dp[a][b][c] = dp[a - 1][b][c] + dp[a - 1][b - 1][c] + dp[a - 1][b][c - 1] - dp[a - 1][b - 1][c - 1];
                    }
                }
            }
        }

        while (true) {
            StringTokenizer st = new StringTokenizer(bf.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;

            if (a <= 0 || b <= 0 || c <= 0) {
                System.out.println("w(" + a + ", " + b + ", " + c + ") = 1");
            } else if (a > 20 || b > 20 || c > 20) {
                System.out.println("w(" + a + ", " + b + ", " + c + ") = " + dp[20][20][20]);
            } else {
                System.out.println("w(" + a + ", " + b + ", " + c + ") = " + dp[a][b][c]);
            }
        }
    }
}