완전탐색 1090 문제 질문드립니다.
for y in arr_y:
for x in arr_x:
제공해주신 코드에서 y,x 각 축을 꼭 다돌아야 하는건가요?
강사님이 설명해주신부분에서 여러명이 한곳에서 모일때 비용을 최소화하기위해서는 여러명중 한명의 집에서 모이면된다. 라는 부분을 참고하면 입력된 4개의 좌표(집)값에 대해
각 좌표 값에대해 나머지 좌표값들의 거리를 계산하면 되는거아닌가요..??
for ex, ey in arr: # [15, 14], [15, 16], [14, 15], [16, 15]
for x, y in arr: # [15, 14], [15, 16], [14, 15], [16, 15]이런식으로요
조언 부탁드립니다.
답변 1
0
반례가 하나 존재합니다!
예를들어 3*3 좌표칸이 있을 때 아래와 같이 집이 있다면 어디에서 모이는게 가장 이득일까요 :
X O X
O X O
X O X
2차원 위에서 계산할때는 각각의 집을 기준으로 계산하면 이와 같은 반례가 발행하기 때문에
X축 기준으로 가능한 위치 * Y축 기준으로 가능한 위치를 계산하는 방법으로 풀어야만 합니다!
ㅎㅎㅎ 매번 나오는 질문이에요! 질문 감사합니다!
dp[x]가 최대값이라고 확신할수 있는 이유
0
46
1
1090번 문제 질문
0
151
1
유니온파인드
0
112
1
투포인터 25:15 질문
1
129
1
#1090번 문제 반례가 궁금합니다.
0
148
1
예제코드 자바입니다
1
187
1
정수론 파트 #2247 문제에 대한 질문입니다!
0
102
0
코드 오류
0
186
1
2강 정수론 문제3 #1407 질문
0
127
0
이차원 배열 (int형)dp로 0 혹은 -1로 체크하는 방법 말고 boolean형 배열로 체크해서 바로 리턴해줄 수 없나요?
0
154
0
1717번 최적화
0
112
0
백준 22988 문제 질문
1
193
2
[Python] 백준 1090번 문제
1
226
3
강의자료에서
1
162
2
2503 문제 제한 조건 질문!
1
249
2
백준 22988 번 문제
1
193
1
추가 강의 순서
1
181
2
(*문제 풀이)1090 테스트케이스 1번 C++
1
221
2
7강 RGB 색칠하기 질문 있습니다.
1
161
2
정수론 약수 빠르게 구하기 질문
1
257
1
1090 문제의 2, 3번째 아이디어는 결국 같은거 아닌가요?
1
375
2
1090 문제 관련하여 맨해튼 거리 최솟값에 대해 질문 있습니다.
1
223
2
누적합 문제 3번 질문
1
216
2
기억 ( 누적합 ) 강의 11660 문제
1
163
2