글 읽기 - 고수님들의 많은 조언 부탁드립니다.. ㅠㅠ

wookii 2년 전 0

고수님들 안녕하세요.

다른 분들께서는 K를 이용해 중간 값을 for문으로 돌면서 값을 구하는데, 저는 조금 다른 방식으로 접근해봤습니다.

한 칸씩 이후, 이전으로 이동하면서 특정 값의 최솟값을 구하는 방식입니다.

논리적으로는 틀린 부분이 없다고 생각했는데, 시작하자마자 틀렸다고 나오는 이유가 분명 있겠지요 ㅠㅠ

많은 조언과 질타 부탁드립니다 ㅠㅠ

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type matrix struct {
	r, c int
}

var (
	w  = bufio.NewWriter(os.Stdout)
	sc = bufio.NewScanner(os.Stdin)
)

var (
	N int
	D [][]int
	A []matrix
	M = 125000002
)

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	defer w.Flush()
	N = scanInt()
	A = make([]matrix, N+1)
	for i := 1; i <= N; i++ {
		A[i] = matrix{
			r: scanInt(),
			c: scanInt(),
		}
	}
	D = make([][]int, N+1)
	for i := range D {
		D[i] = make([]int, N+1)
		for j := range D[i] {
			if i == j {
				D[i][j] = 0
			}
			D[i][j] = M
		}
	}
	fmt.Fprintln(w, solve(1, N))
}

func solve(i, j int) int {
	if i > j {
		return 0
	}
	if i+1 == j {
		D[i][j] = A[i].r * A[i].c * A[j].c
		return D[i][j]
	}
	if D[i][j] != M {
		return D[i][j]
	}
	pre := solve(i, j-1) + (A[i].r * A[j-1].c * A[j].c)
	post := solve(i+1, j) + (A[i].r * A[i+1].c * A[j].c)
	D[i][j] = min(pre, post)
	return D[i][j]
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func scanInt() int {
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	return n
}

func scanInts() []int {
	sc.Scan()
	t := strings.Fields("0 " + sc.Text())
	res := make([]int, len(t))
	for i := range t {
		res[i], _ = strconv.Atoi(t[i])
	}
	return res
}

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

문제

문제

출처

ICPC

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

wookii 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말