글 읽기 - 1027번 문제 질문

kmh0422 9년 전 0

제가 테스트한 케이스에 대해서는 맞게 작동하는 것 같은데 오답이 나와서 질문 드려요.

각 빌딩에 대해 나머지 빌딩들을 볼 수 있는지 여부를 전부 확인하는 방식인데요.

두 빌딩의 지붕을 지나는 직선의 방정식을 구하고, 두 빌딩 사이의 빌딩들이 그 직선을 지나는지 여부를 확인했습니다.

어떤 부분에서 오류가 생기는지 알려주세요.

#include <stdio.h>
#include <math.h>
#define SLOPE(x1, x2, y1, y2) ((double)(y2 - y1) / (double)(x2 - x1));
#define SWAP(t, x, y) {t = x; x = y; y = t;}
#define MAX(a, b) (a > b) ? (a) : (b);

int N, height[55];

int maxVisible();
int isVisible(int from, int to);

int main()
{
	int i, ans;

	scanf("%d", &N);
	for(i = 1; i <= N; i++) {
		scanf("%d", &height[i]);
	}
	ans = maxVisible();
	printf("%d\n", ans);

	return 0;
}

int maxVisible() {
	int i, j, cnt, ret = 0;

	for(i = 1; i <= N; i++) {
		cnt = 0;
		for(j = 1; j <= N; j++) {
			if(i == j)	continue;
			if(isVisible(i, j)) {	// i에서 j 볼 수 있는지 여부 확인
				cnt++;
			}
		}
		ret = MAX(ret, cnt);
	}

	return ret;
}

int isVisible(int from, int to) {
	double m = SLOPE(from, to, height[from], height[to]); 
	int i, tmp;

	if(from > to)
		SWAP(tmp, from, to);

	for(i = from + 1; i < to; i++) {
		if(m * (double)(i - from) + (double)height[from] <= (double)height[i])
			return 0;	
	}
	
	return 1;
}

pichulia 9년 전 0

역시 가장 큰 원인은 그거겠죠? 직선에 접하는지 판별할 때 double을 사용했다는거...

double을 쓰지 않고 답을 구하는 법을 찾아봅시다

kmh0422 9년 전 1

pichulia 님, double을 사용하는 것이 왜 문제가 있는지 잘 이해가 안 됩니다.. ㅠㅠ

그 부분에 문제가 있다고 하셔서 부등식을 풀어서 double 형을 사용하지 않는 방식으로

코드를 다시 수정해 봤는데, 이 방법도 소용이 없었어요.

조금 더 자세히 설명해 주시면 안될까요?

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

문제

문제

출처

ICPC

1027번 문제 질문

kmh0422 9년 전 0

pichulia 9년 전 0

kmh0422 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말