husy951   2년 전

메모리 초과라고 합니다! 어느 부분을 수정해야할까요?

bupjae   2년 전

입력이 10만개에 가까우면 j 배열의 크기는 약 50억이 됩니다. int 하나당 4byte 라고 하면 약 19기가바이트 의 메모리를 요구하게 됩니다.

j 배열 없이 답을 구하는 방법을 찾아보세요

husy951   2년 전

@bupjae

어이구야... 50억... 엄청나네요.. 다시 생각해보겠습니다!

husy951   2년 전

@bupjae

j벡터를 지우고 해봤는데, 시간초과나네요... 반복문을 하나만 써서 해야하나요??


#include<iostream>
#include<vector>
#include<algorithm>


using namespace std;
int main() {

 vector<int> i;
 int t;
 int n;
 cin >> t;
 for (int z = 0;z < t;z++) {
  cin >> n;
  i.push_back(n);
 }
 int park = i.size();
 park--;
 long long sum = 0;
 for (int a = 0;a < park;a++) {
  for (int b = a + 1;b < i.size(); b++) {
   
   sum += i[a] * i[b];
   
  }
 }
 
 cout << sum;
 return 0;
}

bupjae   2년 전

이제 50억개 크기의 배열은 쓰지 않고 있지만 계산은 여전히 50억번을 하고 있습니다.


이 문제는 2중 반복문 없이 1중 반복문민으로 풀 수 있습니다. 분배법칙을 잘 활용해 보세요.

댓글을 작성하려면 로그인해야 합니다.