글 읽기 - 15732번 관련해서 여쭤보고 싶습니다...

parkpkww 3년 전 0

안녕하세요.

풀다가 이해가 잘 안되는 점이 있어서 질문을 드리고 싶습니다.

제가 생각하기에는 똑같은 두 코드가 하나는 'AC'를 받고, 하나는 '틀렸습니다'가 뜹니다.

어떤 차이점이 있는지 곰곰히 생각해보았으나, 알 수가 없어서 이렇게 질문드립니다...

고수님들 저에게 가르침을 주시면 감사하겠습니다.

(아래에는 어쩔 수 없이 AC를 받은 코드를 적었습니다. 아직 문제를 푸시지 않은 분들은 주의해주세요...!)

AC 를 받은 코드와 그렇지 못한 코드는 차례로 아래와 같습니다.

두 코드의 차이점은 19~23 or 73~77 줄 입니다.

범위를 설정함에 있어서 간단히 해주고 싶어서 19~23줄을 73~77줄과 같이 코딩을 하였으나 계속 틀렸습니다.

데이터를 처리함에 있어서 제가 미숙하여 모르는 어떤 이유에서 이러한 문제가 발생한 것 같습니다...

혹시 이유를 알려주실 수 있을까요..?

////////////////////////////// AC 받은 코드 //////////////////////////////
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long ll;

int N, K, D, ans;
tp rule[10005];

bool ok(int x) {
	ll cnt = 0LL; // x 이하의 도토리 저장 개수 ( int 범위 넘어갈 수 있음 )
	for (int i = 0; i < K; ++i) {
		// s이상 e이하 d 거리 간격으로 도토리 심는다.
		int s = get<0>(rule[i]);
		int e = get<1>(rule[i]);
		int d = get<2>(rule[i]);
		if (x < s) continue;//범위 안들어옴

		//x = min(x, e);
		//cnt += 1LL * ((x - s) / d + 1);

		if (x > e) cnt += 1LL*((e - s) / d + 1); // 시작 점에 심고 시작하니 + 1
		else cnt += 1LL*((x - s) / d + 1);
	}

	if (cnt >= D) return true;
	return false;
}

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

cin >> N >> K >> D;
for (int i = 0; i < K; ++i) {
	int a, b, c;
	cin >> a >> b >> c;
	rule[i] = tp(a, b, c);
}

int l = 0;
int r = N;
while (l <= r) {
	int mid = (l + r) / 2;

	if (ok(mid)) {
		ans = mid;
		r = mid - 1;
	}
	else l = mid + 1;
}
cout << ans << '\n';

return 0;
}

////////////////////////////// 틀린코드 //////////////////////////////
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long ll;

int N, K, D, ans;
tp rule[10005];

bool ok(int x) {
	ll cnt = 0LL; // x 이하의 도토리 저장 개수 ( int 범위 넘어갈 수 있음 )
	for (int i = 0; i < K; ++i) {
		// s이상 e이하 d 거리 간격으로 도토리 심는다.
		int s = get<0>(rule[i]);
		int e = get<1>(rule[i]);
		int d = get<2>(rule[i]);
		if (x < s) continue;//범위 안들어옴

		x = min(x, e);
		cnt += 1LL * ((x - s) / d + 1);

		//if (x > e) cnt += 1LL*((e - s) / d + 1); // 시작 점에 심고 시작하니 + 1
		//else cnt += 1LL*((x - s) / d + 1);
	}

	if (cnt >= D) return true;
	return false;
}

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

cin >> N >> K >> D;
for (int i = 0; i < K; ++i) {
	int a, b, c;
	cin >> a >> b >> c;
	rule[i] = tp(a, b, c);
}

int l = 0;
int r = N;
while (l <= r) {
	int mid = (l + r) / 2;

	if (ok(mid)) {
		ans = mid;
		r = mid - 1;
	}
	else l = mid + 1;
}
cout << ans << '\n';

return 0;
}

whdgurclzls 3년 전 1

반복문을 도는동안 x의 값이 자꾸 갱신 되어서, 원래의 비교하고자 하는 x(함수 호출시 처음 받은 인자)를 비교하는게 아니고 변경된 x와 비교를 하는듯 합니다.

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