완전탐색 강의 1090번 문제 풀이 방법 의문
976
작성한 질문수 2
완전탐색 강의 마지막 문제 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개의 좌표를 확인해야 합니다 :)
해당 부분 확인해보시고 계속 의문이 남으신다면 또 답글 달아주세요!
dp[x]가 최대값이라고 확신할수 있는 이유
0
41
1
1090번 문제 질문
0
147
1
유니온파인드
0
111
1
투포인터 25:15 질문
1
126
1
#1090번 문제 반례가 궁금합니다.
0
145
1
예제코드 자바입니다
1
184
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
99
0
코드 오류
0
184
1
2강 정수론 문제3 #1407 질문
0
123
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
153
0
1717번 최적화
0
111
0
백준 22988 문제 질문
1
191
2
[Python] 백준 1090번 문제
1
223
3
강의자료에서
1
160
2
2503 문제 제한 조건 질문!
1
247
2
백준 22988 번 문제
1
190
1
추가 강의 순서
1
178
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
219
2
7강 RGB 색칠하기 질문 있습니다.
1
159
2
정수론 약수 빠르게 구하기 질문
1
254
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
370
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
218
2
누적합 문제 3번 질문
1
213
2
기억 ( 누적합 ) 강의 11660 문제
1
160
2