글 읽기 - 형님들 반례좀 부탁드리겠습니다

devbelly 4년 전 0

안뇽하세여 형님들, 예제만 통과하고 게시판에 반례가 없어서 질문 드립니다 ㅜ 혼자 힘으로 풀고싶은데

반례 또는 완전히 틀려먹은거 같이 생겼다면 다시풀라고 알려주실수 있나요?

손으로 작은 입력들도 몇개 넣어봤습니당

#include <bits/stdc++.h>
using namespace std;

const int INF = 10001;
int n, m;
vector<int> wk;
int cache[10001][2][3];

int solve(int a, int b, int c) { 
	if (a < 0) return INF; // 짜장면을 많이 요리한 경우
	if (c > 2) return INF; // 손이 3개이상 되는 경우
	if (a == 0) return 1; // 짜장면을 알맞게 요리한 경우,
	if (b == m) {
		if (c == 0) return INF;
		return solve(a, 0, 0) + 1;
	}
	int& ret = cache[a][b%2][c];
	if (ret != -1) return ret;
	ret = min(solve(a - wk[b], b + 1, c+1), solve(a, b + 1, c));

	return ret;
}

int main() {
	cin.tie(NULL);cout.tie(NULL);
	ios::sync_with_stdio(false);
	memset(cache, -1, sizeof(cache));

	cin >> n >> m;
	wk = vector<int>(m);
	for (int i = 0;i < m;++i)
		cin >> wk[i];
	int ans = solve(n, 0, 0);
	if (ans >= INF) cout << -1;
	else cout << ans;



	return 0;
}

newdeal 4년 전 3

안녕하세요.

반례 첨부해드립니다.아마 dp함수 선언이 잘못된 것 같습니다. 예제말고 다른 데이터 몇개 넣어봤는데 다 안되는 것 같아서..

이 반례말고 다른 반례나 힌트 필요한거 있으시면 태그해주세요 :)

6 3
1 2 3
//ans:2
100 5
1 2 3 4 5
//ans:12
17 3
1 1 3
//ans:5
1007 5
1 2 3 4 5
//ans:112
9217 6
1 1 2 2 3 3
//ans:1537

devbelly 4년 전 0

앗 감사합니다 형님 동시에 두개밖에 요리가 안되는 거였군용 다시 풀어보고 오겠습니다

devbelly 4년 전 0

@newdeal
형님 제 실력으론 무린거 같습니다 조금만 더 도와주시면 감사하겠습니다. 본문에 수정한대로 다시 작성했는데 무엇이 문제일까요?

newdeal 4년 전 1

이 문제는 전처리를 해주면 cache[10001], 1차원배열 선언만으로 풀수있습니다.

그 전처리는 한개,두개의 웍으로 만들 수 있는 만들 수 있는 요리의 크기를 미리 저장해두는 것 입니다.

예를 들어, 1 3 5 총 3개의 웍이 있다면 만들 수 있는 요리의 크기의 경우의 수는 1,3,4,5,6,8,9가 있겠네요.

이렇게 미리 경우의 수를 저장해두고 가방문제처럼 접근하시면 될 것 같습니다.

devbelly 4년 전 1

@newdeal
크윽 감사합니다 핑계가 아니라 첨에 그생각했는데 동시에 요리가 2개 이상도 되는줄 알아서 전처리는 안된다고 생각했습니다 감사합니다!!

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

문제

문제

출처

ICPC

형님들 반례좀 부탁드리겠습니다

devbelly 4년 전 0

newdeal 4년 전 3

devbelly 4년 전 0

devbelly 4년 전 0

newdeal 4년 전 1

devbelly 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말