dev/algorithm

BOJ / 9184번 / 신나는 함수 실행 [Go][Python3]

crscnt 2021. 3. 5. 21:00

👩🏻‍💻 문제

 

9184번: 신나는 함수 실행

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

www.acmicpc.net


✍🏻 í’€ě´

🎨 Go

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

import (
	"bufio"
	"fmt"
	"os"
)

var (
	dp [][][]int
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for {
		var a, b, c int
		fmt.Fscanln(reader, &a, &b, &c)
		if a == -1 && b == -1 && c == -1 {
			break
		}
		dp = make([][][]int, 21)
		for i := 0; i < 21; i++ {
			dp[i] = make([][]int, 21)
			for j := 0; j < 21; j++ {
				dp[i][j] = make([]int, 21)
			}
		}
		fmt.Fprintf(writer, "w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c))
	}
}

func w(a, b, c int) int {
	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]
}

🎨 Python3

# https://www.acmicpc.net/problem/9184
import sys

dp = [[[0 for i in range(21)] for j in range(21)] for k in range(21)]

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    if dp[a][b][c] != 0:
        return dp[a][b][c]
    if a < b and 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]

if __name__ == "__main__":
    while True:
        a, b, c = list(map(int, sys.stdin.readline().split()))
        if a == -1 and b == -1 and c == -1:
            break
        print("w({}, {}, {}) = {}".format(a, b, c, w(a, b, c)))
728x90