글 읽기 - 고수님들께.. 반례를 찾지 못하겠습니다. (50%에서 틀렸습니다)

wookii 3년 전 0

안녕하세요.

golang으로 풀었는데, 예제는 다 맞았다고 나오지만 제출하면 50% 부근에서 틀렸습니다가 뜨네요.

다른 분들은 재귀와 DP를 적절히 섞으셨던데, 저는 그냥 재귀를 아예 제거하고 DP로만 풀어보았습니다.

하지만 틀린 부분이 어디인지 도저히 찾을 수가 없네요..

고수님들의 많은 훈계와 조언 부탁드립니다 ㅠㅠ

감사합니다!

package main

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

var (
	w   = bufio.NewWriter(os.Stdout)
	r   = bufio.NewReader(os.Stdin)
	arr [][][]int
)

func main() {
	defer w.Flush()
	arr = make([][][]int, 51)
	for i := range arr {
		arr[i] = make([][]int, 51)
		for j := range arr[i] {
			arr[i][j] = make([]int, 51)
		}
	}
	var a, b, c int
	for {
		fmt.Fscanf(r, "%d %d %d\n", &a, &b, &c)
		if a == -1 && b == -1 && c == -1 {
			break
		}
		fmt.Fprintf(w, "w(%d, %d, %d) = %d\n", a, b, c, wFunc(a, b, c))
	}
}

func wFunc(a, b, c int) int {
	if a <= 0 || b <= 0 || c <= 0 {
		return 1
	}
	if arr[a][b][c] != 0 {
		return arr[a][b][c]
	}
	for i := 0; i < 51; i++ {
		for j := 0; j < 51; j++ {
			for k := 0; k < 51; k++ {
				if i == 0 || j == 0 || k == 0 {
					arr[i][j][k] = 1
				} else {
					if i > 20 || j > 20 || k > 20 {
						arr[i][j][k] = arr[20][20][20]
					} else if i < j && j < k {
						arr[i][j][k] = arr[i][j][k-1] + arr[i][j-1][k-1] - arr[i][j-1][k]
					} else {
						arr[i][j][k] = arr[i-1][j][k] + arr[i-1][j-1][k] + arr[i-1][j][k-1] - arr[i-1][j-1][k-1]
					}
				}
				if i == a && j == b && k == c {
					return arr[i][j][k]
				}
			}
		}
	}
	return arr[a][b][c]
}

hash1018 3년 전 2

반복분 제일 안쪽 k부터 도는데 1 1 21일때 arr[20][20][20] 값이 구해져있을까요?

wookii 3년 전 0

@hash1018 님

정말 감사합니다. 생각해보니 정말 그렇네요! 덕분에 잘 해결하였습니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들께.. 반례를 찾지 못하겠습니다. (50%에서 틀렸습니다)

wookii 3년 전 0

hash1018 3년 전 2

wookii 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말