인프런 커뮤니티 질문&답변
작성한 질문수
6주차 6-B 2343 질문있습니다.
해결된 질문
작성
·
28
0
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100004];
int ret = 1e6;
bool check(int e) {
int sum = 0; int cnt = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] > e) {
cnt++;
sum = a[i];
}
else {
sum += a[i];
}
}
if (sum != 0)cnt++;
return cnt <= m;
}
int main() {
cin >> n >> m;
int l = 0; int r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
r += a[i];
}
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ret = min(ret, mid);
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ret;
}이 코드로 제출했을때 계속 중간에서 막혔습니다.
해서 범위가 잘못됬나 싶어서
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[100004];
long long ret = 1e9;
bool check(long long e) {
int sum = 0; int cnt = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] > e) {
cnt++;
sum = a[i];
}
else {
sum += a[i];
}
}
if (sum != 0)cnt++;
return cnt <= m;
}
int main() {
cin >> n >> m;
long long l = 0; long long r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
l = max(l, a[i]);
r += a[i];
}
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) {
ret = min(ret, mid);
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ret;
}
longlong 으로 바꿔서 실행한 결과 통과가 됬습니다. 하지만 int 형으로는 왜 풀리지 않는지 이해가 가지 않아서 질문드립니다. 충분히 int로도 풀려야 하는거 아닌가요?
이해가 가질 않아서 질문드립니다.
하다보니 벌써 6주차네요. 항상 좋은 강의 감사합니다. ㅎㅎ
답변 2
0
안녕하세요 16님 ㅎㅎ
long long은 필요치 않습니다.
제 생각에 2번 코드가 통과한 이유는
1번, 2번 코드의 차이점에는 long long 이외에도 max 부분, 초기값의 차이점이 있기 때문입니다.
int의 최대값은 1e6이 아닌 1e9를 써야 합니다.
한번 2번 코드를 long long을 쓰지 않고 풀도록 수정해보면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100004];
int ret = 1e9;
bool check(int e) {
int sum = 0; int cnt = 0;
for (int i = 0; i < n; i++) {
if (sum + a[i] > e) {
cnt++;
sum = a[i];
}
else {
sum += a[i];
}
}
if (sum != 0)cnt++;
return cnt <= m;
}
int main() {
cin >> n >> m;
int l = 0; int r = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
l = max(l, a[i]);
r += a[i];
}
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ret = min(ret, mid);
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ret;
}이렇게 해보시겠어요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다.
16wjdekdms님, 질문에 대한 답변 드리겠습니다.
C++에서 int형은 일반적으로 32비트 크기로, 약 -2,147,483,648부터 2,147,483,647까지의 정수를 표현할 수 있습니다. 반면 long long은 64비트 크기이므로 훨씬 더 큰 범위의 숫자(-9,223,372,036,854,775,808부터 9,223,372,036,854,775,807까지)를 표현할 수 있습니다.
문제에서 각 원소의 합 r이 int 범위를 초과하는 경우가 발생하면, int형으로는 범위를 감당할 수 없게 되어 잘못된 결과를 초래할 수 있습니다. 이는 특히 r를 계산할 때나 mid를 계산할 때 오버플로우를 유발할 수 있습니다.
int형으로 오버플로우가 발생할 수 있는 가능성:
r값을 계산할 때: 배열a의 모든 수의 합이int의 최대값을 넘는 경우, 오버플로우가 발생할 수 있습니다.
mid값을 계산할 때: 너무 큰 값에서 나누거나 연산하는 과정에서 오버플로우가 발생할 수 있습니다.
따라서, a 배열의 값이 큰 경우나 n 값이 큰 경우에는 long long을 사용하는 것이 안전합니다. 이로 인해 오버플로우를 방지하여 더 큰 값을 정확히 처리할 수 있습니다. int로도 될 수 있지만, 문제에 따라 값의 범위가 매우 클 경우 발생하는 오버플로우를 방지하기 위해 long long을 사용함이 일반적인 해결책이 되기도 합니다.
이해가 가시길 바랍니다. 추가로 더 궁금한 점이 있으시면 언제든지 질문해 주세요. 😊