글 읽기 - C++ 85%쯤에서 틀리는데 반례가 있을까요?

eddy5360 3년 전 0

85%쯤에서 틀리는데 반례가 있을까요?

왜 틀렸다고 나오는지 모르겠네요..

도움 주시면 감사하겠습니다 !

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

const int MAX = 1e5 + 5, INF = 987654321;
int N, arr[MAX];

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", arr + i);
	sort(arr, arr + N);

	// 주어진 나무 간격 중 가장 작은 간격
	// 바뀌지 않는 값이기 때문에 나무 간격의 범위는 [1, minGap] 입니다.
	int minGap = INF;
	for (int i = 1; i < N; ++i) minGap = min(minGap, arr[i] - arr[i - 1]);

	int result = INF;

	// 최대 간격부터 1까지 반복합니다
	for(int gap = minGap; gap > 0; --gap) {
		// top: 최근에 심은 나무 위치
		// arrIdx: 처음에 주어진 나무 위치를 저장하는 배열인 arr에서 하나씩 심기위해 index변수
		// plantCnt: 새롭게 심는 나무의 개수를 저장하는 변수
		int top = arr[0], arrIdx = 1, plantCnt = 0;

		// 기존에 주어진 나무를 다 심어야 끝납니다.
		while (arrIdx < N) {

			// 새로 심을 나무의 위치가 기존의 나무보다 앞에 있을 경우 새로 심어줍니다.
			if (top + gap < arr[arrIdx]) {
				top += gap;
				plantCnt++;
			}

			// 새로 심을 나무의 위치가 기존의 나무보다 뒤에 있으면 기존의 나무를 심어줍니다.
			else if (top + gap > arr[arrIdx]) {
				// 기존의 나무를 심을 때 간격이 안맞으면 break 합니다.
				if (top + gap != arr[arrIdx]) break;
				top = arr[arrIdx];
				arrIdx++;
			}

			// 새로 심을 나무의 위치와 기존의 나무와 위치가 같다면 기존의 나무를 심어줍니다.
			else { // top + gap == arr[arrIdx]
				top = arr[arrIdx];
				arrIdx++;
			}
		}
		// 주어진 나무 끝까지 다 심은 경우에 result를 갱신한다.
		if (arrIdx == N) {
			result = min(result, plantCnt);
			break;
		}
	}
	printf("%d\n", result);

	return 0;
}

sonjaewon 3년 전 0

저같은 경우에는

가로수 가각의 거리의 차를 구해서,

유클리드 호제법으로 GCD 구해서 풀었습니다.

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

문제

문제

출처

ICPC

C++ 85%쯤에서 틀리는데 반례가 있을까요?

eddy5360 3년 전 0

sonjaewon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말