[백준 11659] 구간 합 구하기 4 [C++]

 

 

 요즘 백준을 안 하다가... 현장 실습에 갔는데 정말 할 일이 없어서! 오랜만에 백준 문제를 풀었습니다. 제대로 알고리즘도 생각해서 푼 건 정말 오랜만이라 더 뿌듯한 기분이네요. 

 

 

백준 11659 링크

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

11659번: 구간 합 구하기 4

 

 

 

1. 문제 

 

 정수 m과 n이 들어온다. 후에 n개의 숫자가 입력된다. 후에 m개의 줄에 숫자가 두 개씩 들어온다. 이때의 숫자들은 n을 넘지 않는다. 들어온 숫자를 각각 a와 b라고 가정했을 때, n의 숫자 중 0 ~ b번째의 숫자합 - 0 ~ a번째 숫자의 합의 구해 출력한다.

 

 

2. 접근

  

 이번 문제는 다행히 읽으면서도 이해하기 쉽습니다. 다른 문제들보다 훨씬 그뭔씹이 덜 하네요. 그래서 해결도 쉬웠던 것 같아요. 

 

 우선 m개의 숫자를 입력받아 배열에 넣어줍니다. 그리고 차례대로 숫자 a, b가 들어오면 for문으로 0부터 a까지의 합을 구하고, 0부터 b까지의 합을 구합니다. 그리고 그 차를 빼주면 될 것 같은데... 시간 초과가 납니다. 시간은 1초인데, m이나 n의 수가 10만까지 들어올 수 있습니다. 만약 m이 10만이 들어와서 그만큼의 숫자를 입력받고, 또 a가 9만이 들어와서 그만큼의 합을 구한다면? 또 b가 10만이 들어온다면? 숫자가 장난 아니게 커지겠죠. 그래서 조금 더 효율적인 알고리즘이 필요합니다.

 

 그러면 어떻게 해야하나... 생각보다 간단합니다. 결국 구하자는 건 0 ~ b의 합 - 0 ~ a의 합이잖아요? (a < b) 그래서 계속 0, 1, 2... 의 합은 중복되어 구하게 됩니다. 그러면 애초에 입력받을 때 합을 구하면서 입력을 받으면? 알고리즘도 간단한데

 

arr[i] = arr[i - 1] + j(입력 받은 값);

 

 

 이런 식으로요! 이러면 애초에 배열에 0 ~ i의 합을 구할 수 있고, 배열의 인덱스 a, b를 입력 받아 arr [b] - arr [a]를 해주면 합을 바로 뺴주는 거니까 더 빠르게 해 줄 수 있습니다.

 

 

3. 풀이

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);	// 입출력 시간 줄이기 
	cin.tie(0);
	cout.tie(0);
    
    int n, m;
    
    cin >> n >> m;	// n과 m 입력
    	
    int* arr = new int[n + 1];	// 동적 배열 선언
    arr[0] = 0;	// 첫 값 0 대입

    for(int i = 1; i < n + 1; i++){	// 0으로 하면 인덱스가 -1이 되므로 1부터
        int num;	// n개의 수 입력 받음
        cin >> num;
        
        arr[i] = arr[i - 1] + num;	// i - 1 의 합과 새로 입력 받은 값을 더함
    }
    
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        
        cout << arr[b] - arr[a - 1] << '\n';	// 인덱스를 받아 차를 구해줌
    }
    return 0;
}

 

 

 

 오랜만에 풀었던 문제인데 생각보다 쉽게 풀려 기분이 좋습니다. 하지만 설명은 제대로 된 것 같지는 않아서 조금 그렇네요... 어쨌든 중요한 원리는 입력을 받았을 때 배열에 입력 받은 값과 전 인덱스의 합을 구해준다!입니다. 이해가 잘 되셨을는지 모르겠습니다. 그래도 풀이는 굉장히 정석적으로 했다고 생각했기 때문에 이 정도로 설명은 끝내도록 하겠습니다. 문제 풀이 화이팅입니당!