-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
44번 질문 있습니다
23.08.15 16:00 작성 조회수 245
0
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;
}
답변을 작성해보세요.
0
김태원
지식공유자2023.08.18
안녕하세요^^
위에 코드는 43번 코드인것 같은데요. 44번은 dis 함수가 위와는 전혀 다르게 해야 합니다. 44번 영상의 설명을 먼저 보시고 다시 코드를 짜보세요.
0
인프런 AI 인턴
2023.08.17
안녕하세요, 인프런 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;
}
이 코드를 실행하면 원하는 결과를 얻을 수 있을 것입니다. 감사합니다.
답변 2