글 읽기 - 코드 오류 피드백 부탁드립니다.

poer123 4년 전 0

게시판에 반례도 모두 적용되는데, 최종 결과에선 틀렸다고 나옵니다.

틀린점 피드백 주시면 너무 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct value {
	int duration, pay;
	value(int a, int b) : duration(a), pay(b) {}
};

int N;
int maxV = -9999;
int visited[16];
vector<value> v;

void dfs(int idx, int total_sum) {
	if (idx > N)
		return;
	else if (idx <= N) {
		maxV = max(maxV, total_sum);
	}
	for (int i = idx; i < N; i++) {
		if (!visited[i]) {
			if (i + v[i].duration <= N) {
				total_sum += v[i].pay;
				visited[i] = true;
				dfs(i + v[i].duration, total_sum);
				visited[i] = false;
				total_sum -= v[i].pay;
			}
		}
	}
	return;
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		int T, P;
		cin >> T >> P;
		v.push_back(value(T, P));
	}

	if (v[0].duration == 1 && N == 1) {
		cout << v[0].pay << endl;
		return 0;
	}
	else if (N == 1 && v[0].duration > 1) {
		cout << 0 << endl;
		return 0;
	}

	for (int i = 0; i < v.size(); i++) {
		visited[i] = true;
		dfs(i + v[i].duration, v[i].pay);
		visited[i] = false;
	}

	cout << maxV << endl;

	return 0;
}

nahwasa 4년 전 0

음.. 그게.. 필요없는부분 일단 빼고 생각해보려 했는데

빼고보니 통과되네욬ㅋㅋㅋ

visited가 무슨 용도인진 모르겠으나 예상하신대로 동작을 안했지 싶습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct value {
	int duration, pay;
	value(int a, int b) : duration(a), pay(b) {}
};

int N;
int maxV = 0;
vector<value> v;

void dfs(int idx, int total_sum) {
	if (idx > N)
		return;
	maxV = max(maxV, total_sum);
	
	for (int i = idx; i < N; i++) {
		dfs(i + v[i].duration, total_sum + v[i].pay);
	}
}

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		int T, P;
		cin >> T >> P;
		v.push_back(value(T, P));
	}

	for (int i = 0; i < N; i++) {
		dfs(i + v[i].duration, v[i].pay);
	}

	cout << maxV << endl;

	return 0;
}

poer123 4년 전 1

아아 너무너무 감사합니다!!

쓸데없는걸 줄여보는 연습도 필요하겠네요

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

문제

문제

출처

ICPC

코드 오류 피드백 부탁드립니다.

poer123 4년 전 0

nahwasa 4년 전 0

poer123 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말