22. 온도의 최대값

    22번 문제   

 

 

    내가 풀이한 답   

  처음에는 이중 순회(for)를 돌아서 코드를 짰다. 하지만 입력값이 10만 이하인 것을 보고 안될것이라고 예상은 했다. 돌려봤지만 역시나 Time Limit이였고 이중 순회를(for) O(루트 N)이나 O(N)으로 접근하는 다른 방법이 필요했다. 곰곰히 생각해보았지만 답이 떠오르지 않아서 강의 초반부를 들었다. 강의를 들었을 때 머리를 뒤통수로 한대 맞은 듯한 느낌이 들었다. 

 

 원리의 핵심은 다음과 같다. 초기값으로 연속적인 며칠에 해당하는 K동안의 합을 구한다. 그리고 그 초기값을 바탕으로 K번째부터 순회(for)를 돌아 K번째에 해당하는 값은 더하고 그 인덱스(처음은 K)에 K값을 뺀 인덱스의 값을 빼준다는 것이다. 

 

 

#include <stdio.h>
#include <stdlib.h>


int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
	
	int n, k, i, temp = 0, max = 0;
	scanf("%d %d", &n, &k);

	int *arr = (int *)malloc(sizeof(int) * n);
	
	for(i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	for(i=0; i<k; i++){
		temp += arr[i];
		max = temp;
	}
	
	for(i=k; i<n; i++){
		temp = temp + arr[i] - arr[i-k];
		if(temp > max) max = temp;
	}
	
	printf("%d", max);
	
	free(arr);
	return 0;
}

 

 결과는 통과하였다.

 

 

    사이트의 답안   

#include<stdio.h>
#include<vector>
using namespace std;			
int main(){
	freopen("input.txt", "rt", stdin);
	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;
}

 

  사이트의 답은 벡터를 사용하였다. 벡터에 대해 정리해보는 시간을 가져야겠다.