-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
질문 있습니다
21.07.27 20:59 작성 조회수 119
0
안녕하십니까 선생님.
저의 경우는, 선생님과 같이 논리적인 최댓값을 미리 계산하여 그 값만큼의 거리를 두면서 모든 말을 각 마굿간에 배치할 수 있다면, 그 값은 실제 최댓값이 가능하다는 논리를 기반으로 해결하였으나,
그때 논리적인 최댓값을 이분검색으로 좁혀나가지 않고,
일단 가능한 가장 큰 최댓값을 구한 후, 1씩 줄여나가는 방법으로 좁혀나갔습니다.
그런데 제가 질문드리고 싶은 부분은, 저의 경우는 일단 첫번째 마굿간의 위치는 무조건 말을 배치시킨다고 가정한 후,
2번째 이후 마굿간 부터 거리를 계산하여, 논리적인 최댓값 이상의 거리라면 그 경우만 말을 배치시켰습니다.
그렇게 구현 한 경우, 채점 폴더는 모두 통과하였지만.
그러면 항상 첫번째 마굿간 위치에는 말이 항상 배치되어야 한다는 가정이 깔리기 때문에, 2번째 이상의 마굿간에 처음으로 말이 배치 되는 경우는 생각하지 않아도 되는지 궁금하였습니다.
그런데 만약 두번째 이상의 마굿간에 처음으로 말이 배치시켰을 때 예측한 논리적인 최댓값 만큼 모든 말을 떨어뜨리면서 말을 배치시키는 것이 가능하다면, 그것은 곧 첫 번째 마굿간에 배치시켰을 떄도 가능해 진다 라고 판단되었습니다.
즉, 2번째 이상 위치에 말을 처음으로 배치시키는 것이 가능한 경우라면, 당연히 1번째 위치에 말을 처음으로 배치시키는 것이 가능하지만 // 논리상 1번째 위치에 처음으로 배치시키는 것이 가능할 때, 2번째 이상의 위치에 처음으로 배치시키는 것이 불가능 할 수 있다 라고 생각이 되었습니다.
따라서 항상 첫번째 위치에 첫번째 말을 배치시키는 방식으로 구현하여도, 놓치는 case는 없다고 판단하였는데, 이렇게 생각하는 것이 맞는지 궁금합니다.
(코드 참고)
#include<stdio.h> #include <stdlib.h> #include<algorithm> void insertionSort(int*arr, int n){ int i, j; int tmp; for(i=1; i<n; i++){ tmp = arr[i]; for(j=i-1; j>=0; j--){ if(arr[j] > tmp) arr[j+1] = arr[j]; else break; } arr[j+1] = tmp; } } int main(){ int N,C; int *stall, *horse; int logical_max; int i, j; //1_1. 마구간의 수 N과 , 말의 수 C를 입력 scanf("%d%d",&N, &C); //1_2. stall[N] 과 horse[C]와 distance[C-1]을 동적할당 stall = (int*)calloc(N, sizeof(int)); horse = (int*)calloc(C, sizeof(int)); //1_3. 사용자로 부터 stall[N]의 element를 입력받음 for(i=0; i<N; i++) scanf("%d",&stall[i]); //2. 일단 stall[N]에 저장된 element를 오름차순으로 정렬할 필요가 있음 insertionSort(stall, N); //3. 논리적으로 가장 인접한 두 말의 거리가 최대가 될 수 있는 논리적인 최댓값을 계산 -> (9 - 1 + 1) / (3-1) == (end - start) / (C-1) int start, end; start = stall[0]; end = stall[N-1]; logical_max = (end-start) / (C-1); //4. 논리적인 최댓값 부터 시작해서 1씩 감소시켜 가면서 실제 최댓값을 구함 // 이때의 implementation specification // stall 배열에 저장된 마굿간의 각 위치에 순차적으로 접근하면서, // 현 시점 마굿간의 위치가 그 이전 시점 마굿간의 위치와logical_max 거리 이상 차이날 때에만, 그러한 마굿간의 위치를 horse배열에 저장한다 // horse배열에 저장한다는 의미는, 해당 위치에 말을 배치신다는 의미로 해석할 수 있다 // 즉 문제의 예시처럼, stall = [1, 2, 4, 8, 9]인 경우 // 일단 1을 horse[idx++]에 위치시킨 후 // 2를 읽어와, 2-horse[idx-1] >= logical_max를 검사한다 //(즉 방금 읽어온 마굿간의 위치가, 그 바로 직전 말을 배치시킨 마굿간의 위치와 거리를 계산했을 때, 논리적인 거리의 최댓값 이상인지 검사) // 만약 조건을 만족하면, 해당 위치에 말을 배치시켜도, logical_max거리만큼 떨어져서 배치시킬 수 있다는 뜻임으로 -> horse[idx++] = tmp // 그렇지 않다면 그냥 넘어간다 -> 이때 idx값이 증가되지 않는다는 것이 point -> 후에 for문을 다 돌았을 때, // idx==C(말의 수)이면 말을 배치시킬 때 logical_max만큼 거리를 띄우면서 배치시킬 수 있다는 뜻 이므로, 그 때의 logical_max가 곧 최댓값 // idx<C 라면 logical_max만큼 거리를 띄우면서 모든 말을 배치시키는 것은 불가능 하였다가 되므로, logical_max를 1줄이고 다시 검사해봐야 함 // 따라서 해당 logical_max값만큼 띄우면서 모든 말을 배치시킬 수 있는지를 검사하는 측면에서 가장 중요한 값은 idx! 이다(배치못시키면 jump하니깐) //즉 1에 배치시킨 후 (2-1)<4 이므로 jump // (4-1) < 4 이므로 jump // 8-1 >= 4 이므로 4에 배치 -> horse[idx++] = tmp; // 9-8<4 이므로 jump //결과적으로 idx==2 < 3 이므로 -> 모든 말을 3만큼 띄우면서 배치시키는 것은 불가능 -> logical_max를 3으로 줄이고 다시 try //1에 배치시킨 후 (2-1) < 3 이므로 jump // (4-1) >=3 이므로 3대입 // 8-4 >=3 이므로 8 대입 // for문이 끝나지도 않았는데 idx==3이 되어 , 어쨌든 3만큼 띄우면서 배치시키는 것이 가능해지면, 3이 곧 가능한 최댓값으로 판명남 int distance, tmp; int idx=0; while(1){ idx = 0; for(i=0; i<N; i++){ tmp = stall[i]; if(idx==0) horse[idx++] = tmp; else{ distance = tmp - horse[idx-1]; if(distance >= logical_max) horse[idx++] = tmp; else continue; } //for문이 다 끝나기도 전에 이미 다 배치가 완료되었다면, 그냥 바로 break해도 됨 -> 가능하단 case가 하나라도 존재하면, // 그떄의 logcial_max가 곧 실제 real_max가 되므로! (그런 logical_max만큼 떨어져서 배치시키는 case가 존재하는지 여부가 관건) if(idx == C) break; } if(idx == C) break; else if(idx < C) logical_max--; } //5. 실질적인, 인접한 말의 거리가 최대가 될 떄의, 인접한 말의 거리 출력 printf("%d\n", logical_max ); free(stall); free(horse); return 0; }
답변을 작성해보세요.
0
답변 1