인프런 커뮤니티 질문&답변
작성한 질문수
완전탐색 강의 1090번 문제 풀이 방법 의문
해결된 질문
작성
·
837
3
완전탐색 강의 마지막 문제 1090번 문제 풀이 방법에 의문이 생겨서 질문 올려봅니다. 강의에서는 우리의 집 중에서 한 곳에 모이면 된다고 풀이를 하셨는데, 예시에 나온
4
15 14
15 16
14 15
16 15
4명이 모이기 위한 최적의 장소는 (15,15)입니다. 백준에서도 이것이 정답 좌표이고. 그래서 혹시 제가 1번 2번 3번 아이디어를 이해하는데에서 잘못 이해한 부분이 있을까 싶어 질문을 올립니다.
(15 14) (15 16) (14 15) (16 15) 중에 하나에 모인다는 말이 아닌것인가요?
답변 2
2
코딩 센세
지식공유자
33분 46초에 해당 질문에 대한 이야기가 나옵니다 :)
저희가 1차원이라고만 생각했을때 N곳의 집이 있다면 정답은 그 N곳 중에 하나에 있다는걸 증명했습니다.
그리고 2차원으로 합친다면 정답이 될 가능성이 있는 좌표는 집의 개수인 N개가 아니라,
X축의 정답 가능성 N개와
Y축의 정답 가능성 N개를
모두 조합한 경우의수인 N × N 개를 확인해서 정답을 찾아야 합니다.
따라서, [ 14,14 ], [14,15 ], [14, 16], [15,14] ... [16,16] 까지 총 9개의 좌표를 확인해야 합니다 :)
해당 부분 확인해보시고 계속 의문이 남으신다면 또 답글 달아주세요!
1
