글 읽기 - 왜 한줄을 추가하면 안되는거죠,,,

wlshddlek 5년 전 0

그 저가 주석을 달아놓은 줄이 있는데,,, 그 줄을 없애면 예제 답이 잘나오거든요?? 그런데 시간초과나서 다이나믹을 쓰려고 한줄을 입력하면 예제 답이 다르게 나오네요.. 왜 그러죠,,,,

#include<iostream>

#include<algorithm>
using namespace std;

int buffer[505][505];
int page[505];
int sum[505];
int func(int start, int end)
{
	if (start == end)
	{
		return 0;
	}
	if (buffer[start][end] != 0)return buffer[start][end];   //이부분을 추가하면 틀리게 나오네요,,

	int minn = 10005;
	for (int mid = start; mid < end; mid++)
	{
		int a=func(start, mid);
		int b=func(mid + 1, end);
		minn = min(minn, a + b);
		
	}
	int sum2 = sum[end] - sum[start - 1];
	
	return buffer[start][end] = minn + sum2;


}
int main()
{
	int test;
	cin >> test;
	for (int i = 0; i < test; i++)
	{
		int n;
		cin >> n;
		for (int j = 1; j <= n; j++)
		{
			cin>>page[j];
		}
		
		sum[0] = 0;
		for (int j = 1; j <= n; j++)
		{
			sum[j] = sum[j - 1] + page[j];
		}
		func(1, n);


		printf("%d ", buffer[1][n]);
	}


	return 0;
}

njw1204 5년 전 1

테스트 케이스가 여러개라 그래요

wlshddlek 5년 전 1

앗 개씹멍청했네요 ㅠ

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

문제

문제

출처

ICPC

왜 한줄을 추가하면 안되는거죠,,,

wlshddlek 5년 전 0

njw1204 5년 전 1

wlshddlek 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말