hsh0324   5년 전

기준 i를 잡고 j와 선분을 그어 ccw를 수행하였습니다.
소스상 기준 i에서 왼쪽만을 탐색하지만 결국엔 전체 탐색이 되므로 양방향 판단은 필요없다고 생각합니다.

문제를 이해못한건가요?
소스와 상관없이 제가 생각하는 input/output 예시 입니다.

- 건물 1개
#input
1
1
#output
0

- 건물 2개 (같은 높이, 다른높이)
#input
2
1 1
OR
2
1 2
#output
1

- 건물 3개 (선분에 접하는 경우)
#input
3
1 2 3
OR
3
1 1 1
#output
1

- 건물 4개 (선분을 긋는 A, B 건물이 같은 높이일때)
#input
4
4 1 2 4
#output
3


djm03178   5년 전

5
5 1 10 1 5

가운데 있는 건물은 모든 건물을 볼 수 있습니다.

dmsrb1002   5년 전

djm03178님

두 건물 A,B사이를 잇는 직선 하나만으로 계산해야하는거 아닌가요?


djm03178   5년 전

가운데 있는 건물을 A라고 하면, 첫 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 두 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 네 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 다섯 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않습니다.

그래서 가운데 있는 건물에 있으면 4개의 다른 건물을 볼 수 있으므로, 답은 4가 됩니다.

dmsrb1002   5년 전

그럼,

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

이 예제에서 정답이 7인 이유는 높이가 7인 건물을 기준으로 왼쪽에 4개의 건물(6까지) + 오른쪽에 3개의 건물(5까지)해서 답이 7인건가요??

djm03178   5년 전

7에서는 다음과 같이 볼 수 있습니다.

1 5 3 2 (6) 3 2 (6) (4) 2 (5) 7 (3) (1) (5)

dmsrb1002   5년 전

아하! 이제 이해했습니다. 답변감사합니다

hsh0324   5년 전

답변 감사합니다.
제가 문제를 잘못 이해했군요ㅠ

잘못된 이해 : 선분 AB를 넘는 건물이 없으면 A~B 사이의 모든 건물을 볼 수 있다고 생각
올바른 이해 : 선분 AB를 넘는 건물이 없으면 A에서 B를 볼 수 있음
1 5 3 2 6-(B) 3 2 6 4 2 5 7-(A) 3 1 5

dmsrb1002   5년 전

와..지금 10번째 넘게 틀렸습니다만 나오네요.. 멘붕,,

어디가 오류일까요??ㅠㅠ

djm03178   5년 전

반례 드립니다.

dmsrb1002   5년 전

와..드디어 맞았습니다.ㅠㅠ 감사합니다!

잘못이해했던점:

9 7 1 7

 output: 2 

correct answer: 3

에서 높이가 항상 높은곳에서 낮은곳으로만 볼 수 있다고 생각하여 9가 볼 수 있는 빌딩은 7(o) , 1(x) , 7(0)로 판단하여 2개로 답을 냄.

제대로 이해했던점:

높이가 낮은곳에서 높은곳으로도 볼 수 있으므로 가장 많이 볼 수 있는 빌딩은 높이가 1인 빌딩으로 9(o), 7(0), 9(o)로 3개의 빌딩을 볼 수 있음.

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