글 읽기 - top-down 방식 구현(해결)

shinbian11 3년 전 0

도대체 뭐가 틀렸을까요...ㅠ

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535

using namespace std;
typedef long long ll;

int n, s, m;
int arr[104];
bool d[104][1004];

void go(int x, int y)
{

	if (x > n)
		return; 

	d[x][y] = true;
	
	if (y - arr[x] >= 0)
	{
		go(x + 1, y - arr[x]);
	}
	if (y + arr[x] <= m)
	{
		go(x + 1, y + arr[x]);
	}
	return;

}

int main()
{
	F_I;

	
	cin >> n >> s >> m;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	memset(d, -1, sizeof(d));
	d[0][s] = true;

	go(0, s);

	int ans = -1;

	for (int i = 0; i <= m; i++)
	{
		if (d[n][i] == true)
		{
			ans = i;
		}
	}

	cout << ans << '\n';

	return 0;
}

shinbian11 3년 전 0

해결했습니다.

if (d[x][y] == true)
return;

라는 메모이제이션 넣는걸 깜빡했네요...ㅠ

if (x > n)
return;

와

d[x][y] = true;

사이에 메모이제이션 코드를 추가하고, main함수에서 d[0][s]=true; (44번째줄)을 제거하면 됩니다.

shinbian11 3년 전 0

43번쨰 memset(d, -1, sizeof(d));도 -1이 아니라 false로 초기화해야 합니다.

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

문제

문제

출처

ICPC

top-down 방식 구현(해결)

shinbian11 3년 전 0

shinbian11 3년 전 0

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말