[백준/C++] 수열 회전과 쿼리

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 수열의 회전에 관한 문제다.

문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다.

 

여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다.

 

수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다)

 

 

먼저 처음에 시작 index를 정한다.

이제 수열의 시작 부분이 k만큼 증가하면 이는 시작 index가 오른쪽으로 이동한 것과 같다.

만약 시작 부분이 k만큼 감소하면 이는 시작 index가 왼쪽으로 이동한 것과 같다.

 

여기서 합을 구하는 범위가 N을 넘어가지 않기 때문에 누적합의 범위를 2*N+1 만큼의 크기로 설정하면 계산이 편하다.

 

아래 그림을 참고하면

시작 index에 b를 더한 값이 N보다 클 경우에도 마찬가지로 쉽게 누적합을 이용해 계산할 수 있다.

 

즉, 누적합의 범위를 2*N+1로 설정하면, 항상 시작 index가 1~N 사이에 있도록 유지할 경우에 index의 범위를 초과하지 않아서 계산이 편리하게 된다.

 

그러므로 시작 index가 항상 1~N 사이에 있도록 시작 index의 범위가 N을 넘어가면 시작 index에 N을 빼 앞으로 보내주고, 1보다 작아지면 N을 더해 뒤로 보내준다.

 

이후 누적합[시작 index+b-1] - 누적합[시작 index-a-2]을 계산해 답을 출력한다.

 

 

​

[아이디어 정리]

1. 수열의 이동은 시작하는 index를 이동해 실제로 수열의 원소를 이동시키는게 아니라 index로 속도를 향상 시킨다.
2. 구간의 합을 빠르게 구하기 위해서 누적합을 이용한다.
3. 누적합을 이용할 때, 범위를 초과하는 index를 쉽게 처리하기 위해 vector의 크기를 2*N+1로 만들고, 수열 a를 두개 붙여서 누적합을 구한다. (a1~aN, a1~aN으로 이루어진 2N 크기의 수열의 누적합을 계산한다.)
4. 시작 index가 항상 1~N사이의 범위에 있도록 유지하고, 구간의 합을 출력한다.

 

 

Code

 

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	long long N, Q;
	scanf("%lli%lli", &N, &Q);
	//1이 왼쪽이동 2가 오른쪽이동 3은 합

	vector<long long> nuA(N + 1, 0);
	long long num;
	for (int i = 1; i <= N; i++)
	{
		scanf("%lli", &num);

		nuA[i] = nuA[i - 1] + num;
	}
	int qN, k, a, b, nowStidx = 0;
	long long da, db, ans;

	for (int q = 0; q < Q; q++)
	{
		scanf("%d", &qN);

		if (qN == 3)
		{
			scanf("%d%d", &a, &b);
			da = nowStidx + a - 1;
			db = nowStidx + b;
			ans = 0;
			if (da > N)
			{
				ans -= nuA[N];
				da -= N;
			}
			if (db > N)
			{
				ans += nuA[N];
				db -= N;
			}
			printf("%lli\n", ans + nuA[db] - nuA[da]);
		}
		else
		{
			scanf("%d", &k);
			k %= N; //몇칸 이동할지
			if (qN == 1)
			{
				nowStidx -= k;
				if (nowStidx < 1)
				{
					nowStidx += N;
				}
			}
			if (qN == 2)
			{
				nowStidx += k;
				if (nowStidx > N)
				{
					nowStidx -= N;
				}
			}
		}
	}

	return 0;
}

 

 

 

Code2

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(0);
    cin.tie(0)->sync_with_stdio(0);

	long long N, Q;
	cin >> N >> Q;
	//1이 왼쪽이동 2가 오른쪽이동 3은 합

	vector<long long> A(N, 0);
	vector<long long> nuA(N+1,0);
	for (int i = 0; i < N; i++) 
	{
		cin >> A[i];
	}
	for (int i = 0; i <N; i++) 
	{
		nuA[i+1] = nuA[i] + A[i];
	}
	long long qN,k,a,b, nowStidx=0;
	long long da, db,ans;

	for (int q = 0; q < Q; q++) 
	{
		cin >> qN;

		if (qN == 3) 
		{
			cin >> a >> b;
			da = nowStidx + a - 1;
			db = nowStidx + b;
			ans=0;
			if (da > N) 
			{
				ans -= nuA[N];
				da -= N;
			}
			if (db > N) 
			{
				ans += nuA[N];
				db -= N;
			}
			cout << ans+nuA[db] - nuA[da] << "\n";
		}
		else
		{
			cin >> k;
			k %= N; //몇칸 이동할지
			if (qN == 1) 
			{
				nowStidx -= k;
				if (nowStidx < 1) 
				{
					nowStidx += N;
				}
			}
			if (qN == 2) 
			{
				nowStidx += k;
				if (nowStidx > N) 
				{
					nowStidx -= N;
				}
			}
		}
	}
	
	return 0;
}

 

 

---

 

처음에 아무리 풀어도 시간초과가 떴다.

분명히 시간 복잡도가 N+Q인데 시간초과가 떠서 혹시 2N크기의 수열을 만들면서 시간초과가 떴나 고민했다.

심지어 파이썬으로 풀어봐도 시간초과가 떠서 처음 문제를 봤을 때 다른 문제로 넘어갔다...

혹시 해서 scanf로 입력을 받았더니 풀렸는데, 알고보니 입출력하는 시간이 오래걸린거였다..

 

Code2에 보면 cout.tie(0)를 사용했던게 눈에 보이는데 아무런 생각없이 입력시간이 아니라 출력시간을 빠르게 하고, 입출력 시간을 줄였다고 생각했다...

나중에 cin.tie(0)을 추가하니 바로 문제가 풀렸다;; 아오...

 

 

31563번: 수열 회전과 쿼리