Game Tech Blog
2559. 수열 본문
[예약 시간 오류] 230816 14:00 업로드 분
[문제]
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
3 -2 -4 -9 0 3 7 13 8 -3
모든 연속적인 이틀간의 온도의 합은 아래와 같다.
이때, 온도의 합이 가장 큰 값은 21이다.
또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,
이때, 온도의 합이 가장 큰 값은 31이다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
[입력]
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.
[출력]
첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.
[TC]
1.TC - Input
10 2
3 -2 -4 -9 0 3 7 13 8 -3
TC - output
21
2.TC - Input
10 5
3 -2 -4 -9 0 3 7 13 8 -3
TC - output
31
[접근]
여러 접근법을 사용해보았다.1. 수열을 뽑아내는 next_permutation 함수로 접근, 뽑아내는 수열이 일수 days 와 같은 사이즈를 갖는다면 합을 구해보는 것으로 진행=> next_permutation 이 제공하지않는 버전인지 멤버에 없는 함수라고해서 포기.
2. 아래 실패 코드로 접근, 단 방식은 여러가지로 진행 i 부터 days 까지 더하거나, days 까지 먼저 인덱스를 위치 시킨 후 0쪽으로 인덱스를 옮겨가면서 값을 구하는 방법=> 단, 어떻게 이동을 시키든, 최대 N*N, 즉 100억의 반복수를 줄이진 못함. 고로 타임 아웃
3. 누적합을 이용해, 구간쿼리 방식으로 구함.
1,2,3,4,5 배열이 주어졌을때 모든 수를 합하는 배열을 만듦.
이전의 psum[i-1] 의 값을 이번input 인 arr[i] 에 더해서 누적합 배열을 만듦.
고로 여기서 3 ~ 5 값을 구하고자 했을때, psum[5] - psum[3] = 이 3 ~ 5의 값을 나타냄.
[코드] - C++
#include<iostream>
using namespace std;
int days;
int N;
int arr[100004] = { 0, };
int psum[100004] = { 0, };
int ret;
int input;
int main()
{
cin >> N;
cin >> days;
ret = INT32_MIN;
for (int i = 1; i <= N; ++i)
{
cin >> input;
arr[i] = input;
}
psum[0] = 0;
for (int i = 1; i <= N; ++i)
{
psum[i] = psum[i - 1] + arr[i];
}
for (int i = 0; i < N+1-days; ++i)
{
int sum = psum[i + days] - psum[i ];
if (ret <= sum)
ret = sum;
}
cout << ret;
return 0;
}
[코드] - 실패 : C++
- 실패 사유 : 타임 아웃
#include<iostream>
using namespace std;
int days;
int N;
int arr[100004] = { 0, };
int psum[100004] = { 0, };
int ret;
int input;
int main()
{
cin >> N;
cin >> days;
for (int i = 0; i < N; ++i)
{
cin >> input;
arr[i] = input;
}
for (int i = 0; i < N- days +1 ; ++i)
{
for (int j = i; j < i + days; ++j)
{
psum[i] += arr[j];
}
}
for (int i = 0; i <= days; ++i)
{
if (ret <= psum[i])
ret = psum[i];
}
cout << ret;
return 0;
}
[결과 및 시도]
[후기]
문제를 얼마 풀지 않았지만, 누적합을 모르면 전혀 풀수없는 문제였다.
1, 2번의 접근식으로 쉽게 풀 수 있다고 생각했는데 상당히 오랜시간과 집중력을 요하는 문제..
핵심인 누적합을 모르면 타임아웃을 빠져나갈 수 없었다.
오랜만에 풀어서 그런지 다시 감을 잡기는 좋은 문제였다.
'Algorithm > 백준 온라인 저지' 카테고리의 다른 글
1076.저항 (0) | 2023.08.17 |
---|---|
1620.나는야 포켓몬 마스터 이다솜 (0) | 2023.08.17 |
9996.한국이 그리울 땐 서버에 접속하지 (0) | 2023.08.08 |
11655.ROT13 (0) | 2023.08.03 |
1159.농구 경기 (0) | 2023.08.02 |