1. 오늘의 학습 키워드

백준 2343-기타 레슨(파라메트릭 서치)

2. 공부한 내용 본인의 언어로 정리하기

• 결정함수는 부등식을 반환해야 함.
• 검색함수에서 무지성으로 m을 반환하는 게 아님. 문제 조건을 잘 읽을 것. 문제에서 '블루레이 크기의 최소'를 물었으므로, l을 반환해야 함.

3. 오늘의 회고

3.1 어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 결정함수에서 강의들을 어떻게 블루레이 배열에 분배할지 고민했습니다.
• 처음에는 강의 배열을 돌면서 강의들을 벡터에 넣어가고, 벡터 사이즈와 m을 비교하였지만, 벡터의 크기가 12가 나오는 등 잘 되지 않았습니다.
• 처음에는 검색의 경계를 l = 1로 잡았습니다. 그러나 블루레이에는 어떤 강의든 들어갈 수 있어야 하므로, l = '강의의 최대값' 으로 잡는 게 맞습니다.

3.2 어떻게 해결했는지

• 강의들을 벡터에 넣는 것이 아니라, 강의들을 누적하다가 mid를 넘는 순간에만 카운트를 해서 블루레이의 개수를 구했습니다.

bool deter(int mid){
    int sum = 0, cnt = 0;
    for(int i = 0; i < n; i++){
        if(sum + a[i] > mid){
            cnt++;
            sum = 0;
        }
        sum += a[i];
    }
    if(sum != 0) cnt++;

    return cnt > m;
}

• 검색함수는 mid값을 결정함수에 넘깁니다. 결정함수는 블루레이 개수가 m보다 큰지 비교합니다. 블루레이 개수가 m보다 크면 범위가 작은 것이므로, 탐색 범위의 값을 늘립니다.

3.3 무엇을 새롭게 알았는지

• 파라메트릭 서치는 문제만 잘 이해해도 반은 푸는 것 같습니다. 구현이 매우 간단하기 때문입니다.
• 역시 결정함수가 중요합니다. 결정함수는 부등식을 넘긴다는 점을 잘 기억해야겠습니다.

3.4 내일 학습할 것은 무엇인지

• 오늘 풀었던 문제를 다시 풀어보고, 삼성 기출문제를 풀 예정입니다.