6-B 질문있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

6-B

작성

231

강사님의 로직이 잘 이해가 가지 않습니다.

처음 문제를 풀 때 모든 블루레이를 사용해야 한다 고 생각해서 계속 오답이 나왔었는데요, 그 부분을 지우고 (cnt가 M과 같다는 조건문을 지우고) mid의 최소를 찾아 이분탐색 시켰더니 결국 통과는 했습니다.

그리고 강사님의 코드를 참고했는데, 동작방식이 잘 이해가 가지 않았습니다. 다음은 강사님 코드의 로직을 이해해보고 제 방식으로 수정해본 코드입니다.

bool check(int mid) {
    if (mx > mid) return false;
    int temp = mid;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (mid - a[i] == 0)
        {
            ++cnt;
            mid = temp;
            continue;
        }
        else if (mid - a[i] < 0)
        {
            ++cnt;
            mid = temp;
            --i;
        }
        else
            mid -= a[i];
    }
    if (mid != temp) cnt++; 
    
    return cnt <= m;
}

else if (mid-a[i]<0) 의 조건문에서 i를 감소시켜서 다시 검사하게끔 하여 n+@의 순회를 합니다.

강사님은 이 부분을 최적화 하셔서 기존 14행과 같은 코드를 만드신 것 같은데요, 제가 제대로 이해한건지 (질의1)

제가 제대로 이해한게 맞다면, 처음부터 n회 순회만 하게끔 의도하셔서 코드를 작성하신건지 (처음 코드를 쓸 때부터 바로 저렇게 짜신건지) 아니면 최적화를 하다가 짜신건지 궁금합니다. (질의2)

저런 발상 자체를 해본적이 없어서 굉장히 낯선 코드를 보는 기분이었네요..

감사합니다.

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

강사님은 이 부분을 최적화 하셔서 기존 14행과 같은 코드를 만드신 것 같은데요, 제가 제대로 이해한건지 (질의1)

>> 네 맞습니다.

한번 그림을 그려봤는데요.

일단은 새로이 생성해야 하는 경우 같은 경우 cnt++, mid = temp가 되는 것은 당연합니다. 삐져나오게 되면.. 못넣게 되니까요.

그리고 일반적인 로직은 계속해서 빼야 하기 때문에 mid - v가 됩니다.

>> 처음부터 저렇게 짰습니다. 저렇게 그림 그리면서 짠 것 같습니다.

저런 발상 자체를 해본적이 없어서 굉장히 낯선 코드를 보는 기분이었네요..

>> 이게 음수를 활용하는 부분이라 그런 것 같은데요. 음수를 만들고 해당 음수를 기반으로 새로이 만들어야 하는 로직을 만들었다고 보시면 됩니다. Maruche님처럼 음수를 만들기전 체킹해서 하는 것도 괜찮고 음수를 기반으로 하는 것도 괜찮습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

Maruche님, 강사님의 로직에 대한 이해와 질문에 대해 상세히 설명해 주셔서 감사합니다.
질문에 대해 답변드리기 이전에, 강사님께서 제공한 원래의 코드나 기타 설명 자료가 없어 정확한 답변이 어려울 수 있음을 양해 부탁드립니다.

질의1에서 언급하신 최적화된 코드 이해 부분과 관련해서는, else if 조건 하에서 mid - a[i] < 0일 때 i를 감소시켜 이전 상태로 되돌리고 다음 반복으로 넘어가기 전에 cnt를 증가시키고 mid를 temp로 초기화하는 것은, 현재 블루레이의 크기(mid)가 현재 강의 길이(a[i])보다 작아 새로운 블루레이로 강의를 담아야 함을 의미합니다. 그리고 mid != temp 조건을 통해 남은 강의가 있다면 추가 해야 하는 블루레이 개수를 고려한 점이 맞습니다.

질의2에 대하여, 처음부터 n회 순회를 목표로 작성했는지, 아니면 초안 후 수정을 통해 최적화를 진행했는지는 강사님의 초기 의도나 코드 개발 과정을 알 수 없기 때문에 명확하게 말씀드릴 수 없습니다. 일반적으로는 코딩테스트나 알고리즘 문제 해결 시 시간복잡도를 고려하여 가능한 반복을 줄이는 방향으로 코드를 작성하려 합니다. 그러나 이것이 처음부터 의도된 것인지, 경험과 여러 번의 시도를 통해 최적화된 것인지는 과정을 알 수 없으면 추측만 가능합니다.

이 질문에 대한 구체적인 해답을 얻고 싶으시다면, 인프런의 수강 전 문의 게시판을 통해 강사님에게 직접 문의를 남기셔도 좋습니다. 해당하는 부분의 링크를 참고해주세요.

강의에 대한 추가적인 질문이나 더 필요한 정보가 있으시다면 언제든 문의해 주세요. Maruche님의 학습에 조금이나마 도움이 되셨기를 바랍니다. 감사합니다.

인프런 커뮤니티 질문&답변

6-B 질문있습니다.