풀이 방법 질문 있습니다.

안녕하세요 선생님. 질문이 길어서 죄송합니다 ㅜㅜ. 구현 부분까지가 너무 난잡하시면, 논리부분만 답변해주셔도 정말 감사할 것 같습니다.

저는 이분검색을 이용하지 않은 채 해결하였는데요,  그냥 넘어가도 괜찮은지, 아니면 이분검색으로 해결해보고 넘어가는게 좋을지 모르겠어서 질문 남기겠습니다. 

(저는 1씩 증가시켜가며 마치 순차탐색처럼 최솟값을 확인하였지만, 선생님께서는 이분검색을 사용하여 건너뛰면서 최솟값을 확인하셨기 때문에, 제가 해결한 방법 보다는,선생님 께서 풀어주신 방법이 시간 복잡도가 더 좋은 것 같은데요, 일단 채점 폴더는 모두 통과했습니다.)

=> 사실 해결 당시 이분검색을 생각하지 못했고, 저한테 좀더 직관적인 방법으로 해결하였는데, 이렇게 해결하는것이 맞는것인지도 잘 모르겠습니다. 

<우선 제가 해결한 논리는 이렇습니다.>

* 문제의 예시처럼 1, 2, 3, 4, 5, 6, 7, 8, 9 분짜리 노래 9개가 들어왔을 때, 이를 3개의 dvd에 분배해야 한다면, 논리적으로 dvd 1개의 용량의 최솟값은 15가 된다

* 따라서 최솟값을 15로 잡고, dvd용량을 15에서 시작하여 1씩 증가시켜 가며,  입력으로 주어진 노래들을 문제 조건에 맞게 분배하였을 때, 가장 먼저 분배가 된 용량이 곧 최솟값이다. 

(15, 16, 17 ... 증가시켜가며 확인해보면, 17이 나옴) 

<구현시 주의사항>

1. 논리적인 최솟값을 구할 때, 문제의 예시처럼 나누어 떨어지는 경우도 있지만, 그렇지 않은 경우도 고려하여, 경우에 따라 올림 연산 수행

2. 논리적인 최솟값 부터 1씩 증가시켜가며 , 실제 최솟값을 찾는 부분 구현시 주의사항 (반례의 경우) 

 -> 저의 경우 선생님이 해결하신 과정과 유사하게

 - 시간을 누적시키다가 min값과 같아지면 그 누적값을 바로 dvd에 분배하고

- 누적시키다가 min값을 초과하면, 초과하기 이전까지만 분배하고, 초과시킨 값은 , 다음 dvd에 누적시켰습니다.

-> 그런데 min값을 추과하는 경우 바로 다음 dvd에 분배하는게 아니라 i--만을 수행하여 다음 iteration에서 다음 dvd에 대입하면서 동시에 새롭게 누적시킨 값이 min을 초과하는지 검사하였습니다.

-> 그러면 반례의 경우에도, 마지막 dvd에 초과시킨 모든 값들이 누적되어, 올바르지 않은 최솟값을 출력하지 않을 수 있었습니다.

(참고용 코드)

int main(){

int N, M;

int *arr, *dvd; // *arr : 입력한 노래의 시간 저장 , dvd : M개의 dvd를 의미  

int i,j;

 

//1_1. N, M입력

scanf("%d%d",&N, &M);

//1_2. arr[N] 동적할당

arr = (int*)malloc(N * sizeof(int));

dvd = (int*)calloc(M , sizeof(int));

//1_3. arr의 element를 입력받음

for(i=0; i<N; i++)

scanf("%d",&arr[i]); 

//2_1.  (arr[N]의 element의 합 / M) 를 수행하여, 이론적으로 가능한 DVD하나의 최소 용량을 구함 

int min, mod;

int sum=0;

for(i=0; i<N; i++)

sum += arr[i];

mod = sum % M;

   // case 1. 나누어 떨어지는 경우 (후처리x) 

if(mod == 0) 

min = sum / M;

  // case 2. 나누어 떨어지지 않는 경우 -> 올림 수행 

else

min = (int)(((double)sum/(double)M)+1);

//2_2. 이후 이론적으로 가능한 최솟값 부터 시작하여 1씩 증가시켜 가며, 실제 가능한 DVD 하나의 최소 용량을 구함 

int cnt;

int sub_sum;

int idx;

while(1){

cnt = 0;      // 분배한 횟수를 count하기 위한 변수  

sub_sum = 0; //실제 분배하기 전, 각 노래 시간의 합  

idx = 0;     // dvd배열에 접근하기 위한 index  

// dvd 배열 초기화 과정  

for(i=0; i<M; i++)

dvd[i] = 0;

// 각 노래를, 최솟값 min값을 기준으로  dvd에 분배 

//  마지막 M-1번째 dvd에 분배할 차례가 아닌 나머지의 경우 

   // ->  각 노래 시간을 누적시켜 가다가, 

          // i) 누적시킨 sub_sum값이 최솟값 min과 같으면 -> 그대로 분배하고 cnt++ 

          // ii) 누적시킨 sub_sum 값이 최솟값 min보다 크게 되면 -> 초과한 시간은 제외하고 나머지 누적값을 분배 후 cnt++ 

  // 이때 i--도 진행하여, 초과시킨 값은 다음 dvd에 분배한다 

   // 마지막 M-1번째 dvd에 분배할 경우

       //앞에서 M-2번째 dvd까지만 분배한 이후, 분배하지 못한 시간들을 모두 누적하여 M-1번째 dvd에 분배  

for(i=0; i<N; i++){

sub_sum += arr[i];

if(cnt < M-1){

if(sub_sum == min){

dvd[idx++] = sub_sum;

sub_sum = 0;

cnt++;

}

else if(sub_sum > min){

dvd[idx++] = sub_sum - arr[i];

sub_sum = 0;

cnt++;

i--;

}

}

if(i == N-1){

dvd[idx++] = sub_sum;

}

}

    // 최솟값 min에 따라 분배했을 때, 확인 과정

  // : 각 dvd에 분배된 시간이 최솟값 min을 초과하였으면 -> 최솟값을 증가시켜 다시 분배해야 함. 

  // 그렇지 않고 모든 dvd에 min값 이하의 시간으로 분배되어 있으면 -> 그때 min이 곧 실제 최솟값  

for(i=0; i<M; i++){

if(dvd[i] > min)

break;

}

if(i==M) break;

else min++;

}

///3. 최소 용량 출력  

printf("%d\n", min);

free(arr); free(dvd);

return 0;

}