글 읽기 - DFS 접근...

seyoung1219 4년 전 0

DFS로 접근해서 테스트케이스는 전부 통과했는데, 채점하면 틀렸다고 뜨네요

제가 반례 찾아볼려고 노력했는데, 반례도 못찾겠고..

고수님들 도와주세요 ㅜㅜ

#include <iostream>
#include <limits.h>
#include <algorithm>

using namespace std;

int N, *T, *P, ans = 0, *visit;

int DFS(int start) {
	if (start >= N || start + T[start] > N){
		return 0;
	}

	int next = start + T[start];
	
	int temp = 0;
	for (int i = next; i < N; i++) {
		if (i + T[i] <= N && visit[i] == 0) {
			visit[i] = 1;
			int result = DFS(i);

			if (result == 0) {
				temp = max(temp, P[i]);
			}
			else {
				temp = max(temp,result);
			}
		}
	}
	return temp + P[start];
}

void solve() {

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	T = new int[N];
	P = new int[N];
	visit = new int[N];
	
	for (int i = 0; i < N; i++) {
		cin >> T[i] >> P[i];
	}

	for (int i = 0; i < N; i++) {
		fill_n(visit, N, 0);
		ans = max(ans, DFS(i));
	}
	

	cout << ans << '\n';
	return 0;

}

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

문제

문제

출처

ICPC

DFS 접근...

seyoung1219 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말