[C++] 온도의 최대값

[목적]

N일간의 온도를 입력받아 K일 간격으로 온도를 더한 값(온도) 중 가장 큰 값을 출력하는 프로그램이다.

 

[입력 예제]

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

 

[출력 예제]

21

10일 동안의 온도를 [3, -2, -4, -9, 0, 3, 7, 13, 8, -3]과 같이 측정하였으며, 이틀간의 온도를 더하여 가장 큰 온도를 알아내야 한다. 

3 + (-2) = 1

-2 + (-4) = -6

.

.

.

7 + 13 = 20

13+8 = 21

8 + (-3) = 5

와 같은 더한 결과를 확인할 수 있으며, 이 중 가장 큰 합은 13과 8을 더한 21이기에 21을 출력한다.

---

[코드 1]

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, k, i, j, sum=0, max=-2147000000; //max값에 0을 줬을 때 영하의 온도를 체크할 수 없어 오류가 났었음.
    
    /*1*/cin >> n >> k;
    
    int t[n];
    
    /*2*/for(i=0; i<n; i++) cin >> t[i];
    
    /*3*/for(i=0; i<=n-k; i++){
        /*4*/sum = 0;
        /*5*/for(j=i; j<k+i; j++) sum += t[j];
        /*6*/if(sum>max) max = sum;
    }
	
    /*7*/cout << max;
	
    return 0;
}

 

[풀이 1]

1. 며칠(n)을 입력받을 것인지 며칠의 합(k)을 구할 것인지 입력받는다.
2. for문으로 n기간 동안의 온도를 배열(t(n))에 입력받는다.
3. 이중 for문을 이용하여 n-k일까지 하루씩 늘려간다. (k일씩 더하기에 k 일을 더할 수 있는 날까지만 반복해준다.)
4. 온도의 합을 받을 sum변수를 0으로 초기화한다.
5. for문을 통해 i일부터 k+i일까지 1일씩 늘려가며 sum변수에 그날의 온도를 더해준다.
6. 더한 sum값이 온도의 합 최댓값(max) 보다 클 경우 max변수에 sum을 넣으며 반복한다.
7. 온도 합의 최댓값인 max를 출력한다.

[실행 결과 1]

2번 결과에서는 왜 오류가 난 지 모르겠다.. 코드에 어떤 문제가 있는지 아시는 분 댓글 부탁드려요...

4번과 5번의 결과는 일 수가 늘어났을 때 시간제한에 걸려 결과를 알 수 없었다 :(

아마 for문을 통해 처음부터 다 더해야 하기에 10000일을 100일씩 더한다 생각하면 for문을 100번씩 100번을 돌려야 해서 시간이 오래 걸리는 것 같다.

 

[+]

2번 문제가 오류 났던 이유는 며칠치 값의 합이 - 값이 나올 수 있는데 처음 내가 max 변수를 0으로 선언하여 오류가 났었다.. ^_^

 

[코드 2]

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int n, k, i, j, sum=0, max=0;
    
    /*1*/cin >> n >> k;
    
    int t[n];
    
    /*2*/for(i=0; i<n; i++) cin >> t[i];
    
    /*3*/for(i=0; i<k; i++) sum += t[i];
    
    /*4*/max = sum;
    
    /*5*/for(i=k; i<n; i++){
        /*6*/sum = sum + t[i] - t[i-k];
        /*7*/if(sum > max) max = sum;
    }
	
    /*8*/cout << max;
	
    return 0;
}

 

[풀이 2]

1. 며칠(n)을 입력받을 것인지 며칠의 합(k)을 구할 것인지 입력받는다.
2. for문으로 n기간 동안의 온도를 배열(t(n))에 입력받는다.
3. 1일(t[0])부터 k일(t[k])까지의 합을 sum에 저장한다.
4. 현재의 최댓값(max)에 sum을 대입한다.
5. k일 부터 시작하여 n일이 되기 전까지 for문을 반복한다.
6. sum에 sum값 + i날의 값 + i일에서 k일을 뺀 값을 넣어준다.
7. 만약 max보다 sum이 크다면 max에 sum을 넣어준다.
8. max를 출력한다.

6번 부과설명

처음 sum과 max에는 k일 만큼 더해진 값이 들어있다.

그러니 sum에 현재까지 더한 일 다음 날을 더하고 sum에 더해진 처음 날짜를 빼게 되면 k일 만큼의 합이 나온다.

 

[실행 결과 2]

 

 

 

문제 출처 : 한국정보올림피아드