백준 11659 : 구간 합 구하기 4

출처 : https://www.acmicpc.net/problem/11659

---

문제

수 N개가 주어졌을때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오

---

생각

1. 0번부터 j까지 합을 구한다음 0부터 j가지의 합을 빼자
2. 누적합을 먼저 구해 놓고 위치 찾아서 빼자

---

코드

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n, m;
    cin >> n >> m;
    vector<int> nums(n + 1, 0);
    
    for(int ix = 1; ix < n + 1; ++ix)
    {
        cin >> nums[ix];
    }
    
    vector<int> results(n + 1, 0);
    
    results[1] = nums[0];
    
    

    for(int ix = 1; ix < n + 1; ++ix)
    {
        results[ix] = results[ix - 1] + nums[ix];
    }

    // for(int ix = 0; ix < n + 1; ++ix)
    // {
    //     cout << results[ix] << " ";
    // }
    
    for(int ix = 0; ix < m; ++ix)
    {
        int a, b;
        cin >> a >> b;
        cout << results[b] - results[a-1] << "\n";
    }
}

---

틀린 이유

• 시간 초과
• cin ,cout 입출력 관련해서 동기화 해제했어야했음
• 문제 철자 틀림 -> 에디터 없으면 어떻게 하려는지

---

수정 코드

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, m, num;
    cin >> n >> m;
    vector<int> results(n + 1, 0);
    
    for(int ix = 1; ix < n + 1; ++ix)
    {
        cin >> num;
        results[ix] = results[ix - 1] + num;
    }
    
    for(int ix = 0; ix < m; ++ix)
    {
        int a, b;
        cin >> a >> b;
        cout << results[b] - results[a-1] << "\n";
    }
}

---

결과

• 문제 풀이 시간 : 25분
• 메모리 :  2804-> 2412 KB
• 시간 :  40 -> 36 ms

  ---

배운점 및 고칠점

• 따로 계산하던 누적합을 입력 받는 동시에 하도록 만듬
• 숫자를 보기 편하개 하기 위해서 n+1 로 배열 길이를 변경
• 좀더 구현을 더 많이 해봐야함, 머리에서 아는거랑 손으로 쓰는건 다르다!
• 처음부터 누적합으로 하면 용량 줄이기 가능하다
• results[ix] = results[ix - 1] + num --> results[ix] += results[ix - 1]