백준 온라인 저지 (Baekjoon Online Judge) - 11441번 : 합 구하기

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

 

#include <stdio.h>
int main() { 
  int num[100001] = { 0 }; 
  int sum[100001] = { 0 }; 
  int n; 
  scanf("%d", &n); 

  for (int p = 1; p <= n; p++)

      scanf("%d", &num[p]); 

   int m; 
   int i, j; 

   scanf("%d", &m); 

   for (int k = 0; k < m; k++) 
   { 
            scanf("%d %d", &i, &j); 

            for (int p = i ; p <= j; p++) 
                    sum[k] += num[p]; 

             i = 0, j = 0; 
     } 

      for (int p = 0; p < m ; p++) 
           printf("%d\n", sum[p]); 

      return 0; 
}

 

처음 코드를 작성할 당시에는 위와 같은 코드를 작성하였다.

그런데, 백준에서는 시간 초과라는 결과를 나에게 주었다.

 

종종 코드의 내용이 올바른 것 같은데 시간 초과가 나는 경우에는

코드 내부적으로 문제가 생겨 문제에서 지정해둔 시간을 초과해버리는 경우를 의미한다.

 

그래서 시간 초과가 나는 이유를 찾아보려고 시도를 해 보았더니,

코드의 초반부에서 각각의 크기가 1,000,001인 배열 num과 sum을 선언했다.

여기에서, 예를 들어서 n에 1,000,001이 입력된 경우를 생각해본다면,

배열 num과 배열 sum은 각각 1,000,001개의 원소를 가지게 된다.

 

이때, 코드 중간 부분의 이중 for 문을 살펴보면,

 

for (int k = 0 ; k < m ; k++)

{

       scanf("%d %d", &i, &j);

       

       for (int p = i ; p < = j ; p++)

            sum[k] += num[p];

      

       i = 0 , j = 0;

}

 

여기에서, 우리는 항상 최악의 상황을 고려해 보아야 한다.

M의 범위는 1 ≤ M ≤ 100,000라고 했기 때문에,

첫 번째 for문은 최대 100,000회 반복될 수 있다.

 

그리고 i의 값에 1이 입력되고 j의 값에 1,000,001이 입력된다고 가정하면,

두 번째 for문은 최대 1,000,001회 반복 될 수 있다.

 

이 코드에서, 이중 for문은 바깥쪽의 for문이 한 번 반복되는 동안

안 쪽의 for문은 1,000,001씩 반복되기 때문에

전체 코드에서 for문의 반복 횟수는

100,000 * 1,000,001 = 100,000,100,000 이 되어

약 1천억 1만 회 for문을 반복하게 된다.

 

우리의 눈으로 보아도 상당히 큰 숫자이다.

문제의 시간 초과를 피하기 위해서라도, 아니면 코드의 효율을 높이기 위해서라도

우리는 동일한 내용을 수행하는 코드들에 대해서 가장 빠른 속도를 가질 수 있도록

코드를 작성해주어야 한다.

 

코드의 실행 속도를 최소화하기 위해서는 여러 가지 방법이 있는데,

최대한 반복문을 사용 횟수를 줄이는 것이 그 방법 중 한 가지이다.

 

처음에 작성한 코드를 보면, 합계를 구하는 for문에서 최대 1,000,001회 반복될 수 있다.

그렇다면, 이 for문을 사용하지 않고도 합계를 잘 처리할 수 있는 방법이 있지 않을까

생각을 해 보았다.

 

여기에서 나는, num 배열에 숫자를 입력할 때 동시에 그 값을 sum 배열에 더해줄 수

있지 않을까라고 생각을 해 보았다.

n에 4가 입력된 경우로 한 번 예시를 들어보도록 하겠다.

 

index	0	1	2	3
num[index]	1	2	3	4
sum[index]	1	3	6	10

 

num 배열에 숫자를 입력할 때 동시에 그 값을 sum 배열에 준다면, 위의 표와 같은 값을 갖게 될 것이다.

여기에서 sum은 해당하는 index까지의 모든 원소들의 합이라고 생각하면 된다.

만약에 i = 3, j = 4가 입력되었다고 했을 때,

3번째 원소와 4번째 원소의 합을 구하고자 하는 것이다.

그런데, 배열의 인덱스는 0부터 시작하기 때문에 배열에서는

2와 3의 index에 해당하는 숫자들의 합을 구해주면 된다.

 

그런데, sum [1]은 원소 하나의 합만을 의미하기 때문에 num[1]과 동일함을 알 수 있다.

우리는 수학에서 Sn = Sn-1 + an (n  ≥ 2)이고, S1 = a1이라는 것을 배운 적이 있었다.

이를 떠올리면 쉽게 이해할 수 있을 것 같다.

 

따라서,

          sum[1] = num [1];

으로 설정해두고 다음 원소들은 일반화를 시켜준다.

 

하나의 원소를 입력받으며, 그 원소를 이전까지의 합에 더해주면,

그 원소까지의 합을 구할 수 있다.

이를 코드로 표현해보면 다음과 같다.

 

for (int i = 2; i <= n; i++)  // n = 4
{ 
      scanf("% d", &num[i]); 
      sum[i] = num[i] + sum[i - 1]; 
}

 

위의 식의 과정을 풀어서 표현해보면,

 

            sum[0] = num[0]

            sum[1] = num[0] + num[1]

            sum[2] = num[0] + num[1] + num[2]

            sum[3] = num[0] + num[1] + num[2] + num[3]

 

이므로

 

            sum[3] - sum[1] = (num[0] + num[1] + num[2] + num[3])

                           -  (num[0] + num[1])

                            = num[2] + num[3]

 

가 되는 것을 확인할 수 있다.

 

이를 일반화하면,

       

           

sum[j] - sum[i-1] = num[i-1] + … + num[i]

가 되는 것을 확인할 수 있다.

 

여기에서, i번째 인덱스의 원소부터 j번째 인덱스의 원소들의 합을 구하기 위해서는,

           

             sum[j] - sum[i-1]을 계산해야 되는 것을 알 수 있다.

 

 

따라서 완성된 코드는 다음과 같다.

 

#include  
int main() { 
     int num[100001] = { 0 }; 
     int sum[100001] = { 0 }; 
     int n; 
     scanf("%d", &n); 

     scanf("%d", &num[1]); 
     sum[1] = num[1]; 

     for (int i = 2; i <= n; i++) 
          { 
              scanf("%d", &num[i]); 
              sum[i] = num[i] + sum[i - 1]; 
           } 

     int m; 
     int start, end; 

     scanf("%d", &m); 

     for (int i = 0; i < m; i++) 
          { 
               scanf("%d %d", &start, &end); 
               printf("%d\n", sum[end] - sum[start - 1]); 
          } 

     return 0; 
}

 

이렇게, 코드의 구현 방식을 바꾸어서 for문을 한 개 덜 사용하면서도 문제를 해결할 수 있었다.

단순하게 코드를 짜는 것 뿐만이 중요한 것이 아니라 코드 작성을 효율적으로 하여 프로그램이

최대한 빠르게 실행될 수 있도록 하는 것 또한 우리가 신경 써야 할 부분이라고 생각한다.

앞으로 코드를 효율적으로 짤 수 있도록 신경쓰도록 해야겠다고 느꼈다.