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