글 읽기 - 반례를 못찾겠습니다...

jobum 2년 전 0

94% 에서 틀려서 경계값에서 에러가 나는 것 같은 느낌인데 계속 틀리니깐 모르겠네요 진짜

어떤 로직으로 풀었냐면

우선 dp를 활용해서 테이프를 최대한 담는 일정의 시작일을 구했습니다

그리고 원하는 테이프를 자르는 값은 2개의 배열로 풀었는데

일정의 개수를 담은 배열

끝나는 날의 개수를 담은 배열

을 이용하여 일정의 시작일 부터 정해진 끝까지 돌면서

주간 달력이 끝나는 날에는 일정의갯수 더하고 ( 왜냐, 이어지는 일정이면 어차피 잘라야되고, 그날 끝나는 것이면 자를 것이기에)

아닌 날에는 일정이 끝나는 날의 개수를 더하여 구했습니다. (이 부분은 81라인부터의 내용입니다)

거의 다 맞는데 뭔가 반례가 있어서 틀리는 거 같은데 못 찾겠어서 질문드립니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static String src="2\n" +
			"9\n" +
			"1 3\n" +
			"5 6\n" +
			"3 8\n" +
			"7 11\n" +
			"49995 50000\n" +
			"49996 49999\n" +
			"49997 50000\n" +
			"49999 50000\n" +
			"49998 49999\n";
	
	static int N, M;
	static int[] scheduleCount;
	static int[] scheduleEnd;
	static int[] dp;

	public static void main(String arg[]) throws IOException {
		//input= new BufferedReader(new InputStreamReader(System.in));
		input= new BufferedReader(new StringReader(src));

		N = Integer.parseInt(input.readLine());
		M = Integer.parseInt(input.readLine());

		int MaxDays = 50001;
		scheduleCount = new int[MaxDays]; // 날의 일정의 갯수 담는 배열
		scheduleEnd = new int[MaxDays]; //끝나는 날 카운트

		StringTokenizer str;

		for (int i = 0; i < M; i++) {
			str = new StringTokenizer(input.readLine());
			int s = Integer.parseInt(str.nextToken());
			int e = Integer.parseInt(str.nextToken());
			scheduleEnd[e]++;
			for (int j = s; j <= e; j++) {
				scheduleCount[j]++;
			}
		}

//		System.out.println(Arrays.toString(scheduleCount));
//		System.out.println(Arrays.toString(scheduleEnd));

		//7일 주력 N 개 일정은 M개,  N개 주력 연속,테이프 자르는 횟수
		//주력에 테이프가 최대한 들어갈 때, 페이프 자르는 수
		//주력에 테이프가 최대한 들어가게 주력 배치 + 주가 끊길때 존재하는 스케줄 갯수 카운팅필요
		int totalDays = N * 7;

		int start = 1;
		int end = MaxDays - totalDays;
		dp = new int[end];

		for (int i = 1; i < 1 + totalDays; i++) {
			dp[1] += scheduleCount[i];
		}
		int maxTape = dp[1];

		for (int i = 2; i < end; i++) {
			dp[i] = dp[i - 1] + scheduleCount[i + totalDays - 1] - scheduleCount[i - 1];

			if (maxTape < dp[i]) { //최대 테이프 갱신시 일정 시작날짜 갱신
				// => 최대인 상태가 2개 이상일 때 가장 먼저인 날짜 기준
				maxTape = dp[i];
				start = i;
			}
		}

//		System.out.println(Arrays.toString(dp));
//		System.out.println(start);

		int cutCount = 0;
		end = start + totalDays;
		for (int i = start; i < end; i++) {

			if ((i - start + 1) % 7 == 0) { //주력이 끊어지는 부분
				cutCount += scheduleCount[i]; // 이날 존재한 스케쥴 갯수 더해줌
				//이날 끝나는 것 + 뒤로 이어지는 일정
			}else{
				cutCount += scheduleEnd[i];
			}

		}
		System.out.println(cutCount);

	}
}

jduck1024 2년 전 1

60번째 줄을

int end = MaxDays - totalDays + 1;

이렇게 고쳤더니 정답으로 처리된 것을 확인할 수 있었습니다.

현재 작성해주신 코드에서는 scheduleCount 배열의 50000번째 원소에 접근할 수 없으며,

50000 50000

과 같은 경우가 반례가 될 수 있을 것 같습니다!

정답 : 1

출력 : 0

jobum 2년 전 0

코드 읽고 틀린 부분 찾아주는게 쉽지 않은 일인데 감사합니닷...! 압도적 감사...!

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

문제

문제

출처

ICPC

반례를 못찾겠습니다...

jobum 2년 전 0

jduck1024 2년 전 1

jobum 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말