글 읽기 - 반례 부탁드립니다.

wlstjd1127 3년 전 0

게시판에 올라와있는 반례들은 다 되는것 같습니다.

14프로 정도에서 틀렸다고 나옵니다.

import java.io.*;
import java.util.*;

public class Main {

	static int N;
	static int[][] day;
	static int max = 0;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		day = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());

			day[i][0] = Integer.parseInt(st.nextToken());
			day[i][1] = Integer.parseInt(st.nextToken());
		}

		for (int i = 0; i < N; i++) {
			if (i + day[i][0] <= N) {
				visited = new boolean[N];
				visited[i] = true;
				DFS(i + day[i][0], visited);
			}
		}

		System.out.println(max);
	}

	static void DFS(int d, boolean[] visited) {
		if (d == N) {
			calMoney(visited);
			return;
		}

		for (int i = d; i < N; i++) {
			int work = i + day[i][0];

			if (work > N) {
				calMoney(visited);
				return;
			}

			visited[i] = true;
			DFS(work, visited);
			visited[i] = false;
		}

	}

	static void calMoney(boolean[] visited) {
		int total = 0;

		for (int i = 0; i < N; i++) {
			if (visited[i]) {
				total += day[i][1];
			}
		}

		max = Math.max(max, total);
	}
}

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

문제

문제

출처

ICPC

반례 부탁드립니다.

wlstjd1127 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말