1027번 - 고층 건물
기준 i를 잡고 j와 선분을 그어 ccw를 수행하였습니다.소스상 기준 i에서 왼쪽만을 탐색하지만 결국엔 전체 탐색이 되므로 양방향 판단은 필요없다고 생각합니다.
문제를 이해못한건가요? 소스와 상관없이 제가 생각하는 input/output 예시 입니다.
- 건물 1개#input 11#output0
- 건물 2개 (같은 높이, 다른높이)#input 21 1OR21 2#output1
- 건물 3개 (선분에 접하는 경우)#input31 2 3OR31 1 1#output1
- 건물 4개 (선분을 긋는 A, B 건물이 같은 높이일때) #input44 1 2 4#output3
55 1 10 1 5
가운데 있는 건물은 모든 건물을 볼 수 있습니다.
djm03178님
두 건물 A,B사이를 잇는 직선 하나만으로 계산해야하는거 아닌가요?
가운데 있는 건물을 A라고 하면, 첫 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 두 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 네 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않고, 다섯 번째 건물을 B라고 해도 그 사이에 아무것도 걸리지 않습니다.
그래서 가운데 있는 건물에 있으면 4개의 다른 건물을 볼 수 있으므로, 답은 4가 됩니다.
그럼,
15 1 5 3 2 6 3 2 6 4 2 5 7 3 1 5
이 예제에서 정답이 7인 이유는 높이가 7인 건물을 기준으로 왼쪽에 4개의 건물(6까지) + 오른쪽에 3개의 건물(5까지)해서 답이 7인건가요??
7에서는 다음과 같이 볼 수 있습니다.
1 5 3 2 (6) 3 2 (6) (4) 2 (5) 7 (3) (1) (5)
아하! 이제 이해했습니다. 답변감사합니다
답변 감사합니다. 제가 문제를 잘못 이해했군요ㅠ
잘못된 이해 : 선분 AB를 넘는 건물이 없으면 A~B 사이의 모든 건물을 볼 수 있다고 생각올바른 이해 : 선분 AB를 넘는 건물이 없으면 A에서 B를 볼 수 있음1 5 3 2 6-(B) 3 2 6 4 2 5 7-(A) 3 1 5
와..지금 10번째 넘게 틀렸습니다만 나오네요.. 멘붕,,
어디가 오류일까요??ㅠㅠ
반례 드립니다.
와..드디어 맞았습니다.ㅠㅠ 감사합니다!
잘못이해했던점:
4
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개의 빌딩을 볼 수 있음.
댓글을 작성하려면 로그인해야 합니다.
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