[Inflearn] 온도의 최댓값(1차원 배열 구간합)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 딱히 떠오르는 방법이 떠오르지 않아 혹시나 하고 풀어보았지만 역시나 시간초과가 발생하였다.. 

     N은 최대 100.000 이고 K 도 최대 100,000 이므로..

     O(N) 의 시간복잡도로 풀는 방법이 필요하다.

     1차원 배열을 탐색하면서 구간합을 구할 수 있는 방법..!

     결국 힌트를 받아버렸다..

     

     n = 10, k = 2

     3 -2 -4 -3 0 3 7 13 8 -3

     를 입력으로 받았다고 해보자.

     먼저 k 의 구간만큼 더해준다. 3 + -2 = 1

     그 다음 index 온도를 더해준 후(1 + (-4) = -3) k 구간에 들어오지 않는 3 을 빼준다. (-3 - (3) = -6)

     보면 -2 + -4 의 결과와 같은 것이 보인다.

     계속 해보자..!

     다음 index -3을 더한 후 (-6 + -3 = -9) 구간에 들어오지 않는 -2 를 빼준다. ( -9 - (-2) = -7)

     이 결과는 -4 + -3 과 같은 것을 볼 수 있다.

  

     이 과정을 식으로 써보면 sum = sum + a[i] - a[i-k]  .

     sum 을 구했으면 max 와 비교해서 최대 합을 찾으면 된다.

     이런 방법은 생각도 못 했는데.. 역시 문제를 많이 풀면서 문제 해결 능력을 키우는게 시급하다..

#. Code

1. 생각없이 푼 시간 초과 코드 BAAAAAAM~!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <cstdio>   int temp[100001];   int main(void) {     freopen("input.txt", "rt", stdin);     int n, k, i, j, max = -2147000000, sum = 0;       scanf("%d %d", &n, &k);       for (i = 1; i <= n; i++)         scanf("%d", &temp[i]);          for (i = k; i <= n; i++)     {         sum = 0;           for (j = i - (k - 1); j <= i; j++)         {             sum += temp[j];         }           max = sum > max ? sum : max;     }       printf("%d\n", max);       return 0; } Colored by Color Scripter

cs

2. 힌트를 얻고..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <cstdio>   int temp[100000];   int main(void) {     freopen("input.txt", "rt", stdin);     int n, k, i, max = -2147000000, sum = 0;       scanf("%d %d", &n, &k);       for (i = 0; i < n; i++)         scanf("%d", &temp[i]);          for (i = 0; i < k; i++)         sum += temp[i];       for (i = k; i < n; i++)     {         sum = sum + temp[i] - temp[i - k];           max = sum > max ? sum : max;     }       printf("%d\n", max);       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include<stdio.h> #include<vector>   using namespace std;               int main(){     int n, k, i, sum=0, res;     scanf("%d %d", &n, &k);     vector<int> a(n);       for(i=0; i<n; i++)         scanf("%d", &a[i]);       for(i=0; i<k; i++)         sum=sum+a[i];       res=sum;       for(i=k; i<n; i++){         sum=sum+(a[i]-a[i-k]);           if(sum>res) res=sum;     }       printf("%d\n", res);       return 0; }

cs

이번에는 배열을 동적으로 생성하는 방법과 유사한 vector를 사용하셨다.

N이 최대 100000이라서 100000크기의 배열을 생성했지만, 작은 데이터들이 들어올 때 메모리 낭비가 되어버리므로

앞으로는 vector 사용을 애용하는 것도 좋을 것 같다. 관련 함수들로 배열에 접근도 더 쉽게 하고..!

#. Result

  - Input --------------------------------------------------------

10 2

3 -2 -4 -9 0 3 7 13 8 -3

------------------------------------------------------------------

  - Output --------------------------------------------------------

21

------------------------------------------------------------------