44번 질문 있습니다

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

44. 마구간 정하기 (이분검색 응용 : 결정 알고리즘)

작성

293

43번 문제는 이제 풀 수 있어서 44번 문제도 43번 처럼 진행했습니다. 그런데 3이 안나오고 다른 답만 나와서요 어디가 잘 못됐는지 알려주실수 있으실까요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m, a[1001];
int dis(int x)
{
    int i,sum=0,cnt=1;
    for(i=1;i<=n;i++)
    {
        if(sum +a[i]>x)
        {
            sum = a[i];
            cnt++;
        }
        else sum=sum+a[i];
    }
    return cnt;
}

int main()
{
    int i,lt,rt=0,max=-2147000000,mid,res=0;
    cin >> n >>m;
    for(i=1;i<=n;i++)
    {
        cin >> a[i];
        rt +=a[i];
        if(max<a[i]) max=a[i];
    }
    lt = a[1];
    while(lt<=rt)
    {
        mid = (lt+rt)/2;
        if(mid>max && dis(mid)<=m)
        {
            res = mid;
            lt = mid+1;
        }
        else rt=mid-1;
    }
    cout << res;
    return 0;
}

c++코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

위에 코드는 43번 코드인것 같은데요. 44번은 dis 함수가 위와는 전혀 다르게 해야 합니다. 44번 영상의 설명을 먼저 보시고 다시 코드를 짜보세요.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요. 제가 제공해드릴 수 있는 도움은 다소 제한적이지만, 최대한 노력해보도록 하겠습니다.

문제의 원인을 찾기 위해 코드를 살펴보았습니다. 코드상으로는 큰 문제가 보이지 않으며, 이분 탐색 알고리즘을 사용하여 문제를 해결하는 것으로 보입니다.

그러나 코드에서 몇 가지 수정이 필요한 부분을 찾았습니다.
1. Dis 함수에서 sum을 0으로 초기화하지 않고 답안에서 제시한 a[1] 값으로 초기화해야 합니다.
2. while문 안의 else문에서 mid에 -1을 하는 것이 아니라 rt 값을 mid-1로 설정해야 합니다.

다음은 수정된 코드입니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, a[1001];
int dis(int x)
{
    int i, sum = a[1], cnt = 1;
    for (i = 2; i <= n; i++)
    {
        if (sum + a[i] > x)
        {
            sum = a[i];
            cnt++;
        }
        else sum = sum + a[i];
    }
    return cnt;
}

int main()
{
    int i, lt, rt = 0, max = -2147000000, mid, res = 0;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        rt += a[i];
        if (max < a[i]) max = a[i];
    }
    lt = a[1];
    while (lt <= rt)
    {
        mid = (lt + rt) / 2;
        if (mid > max && dis(mid) <= m)
        {
            res = mid;
            lt = mid + 1;
        }
        else rt = mid - 1;
    }
    cout << res;
    return 0;
}

이 코드를 실행하면 원하는 결과를 얻을 수 있을 것입니다. 감사합니다.

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

44번 질문 있습니다