[2018 Goricon(경북대 알고리즘 대회)/c++]:17499번 수열과 시프트 쿼리

https://www.acmicpc.net/problem/17499

17499번: 수열과 시프트 쿼리

Goricon에서 다른 문제들도 있었지만, 이 문제 유형은 알아두고 방법을 익히면 다른 같은 유형의 문제들도 쉽게 해결 할 수 있을거라는 판단이 들어 이 문제에 대한 풀이를 적어보고 완벽히 익혀보고자 한다.

---

문제 해석

---

 

어떤 한 수열을 입력받은 후, 1번을 입력받았을 땐 한 수에 x 만큼 값을 추가, 2번을 입력받았을땐 오른쪽으로 이동, 3번은 왼쪽으로 이동하여 최종적으로 변화된 수열을 출력하는 문제이다. 

---

코드

---

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include <tuple>
#include <string>
using namespace std;
long long a[200000];
int N, Q;
int x;
int start_point = 0;
int k, add_item;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < Q; i++) {
		cin >> x;
		if (x == 1) {
			cin >> k >> add_item;
			k -= 1;
			a[(start_point + k) % N] += add_item;
		}
		else if (x == 2) {
			cin >> k;
			start_point = (start_point + N - k) % N;
		}
		else if (x == 3) {
			cin >> k;
			start_point = (start_point + k) % N;
		}
	}

	for (int i = 0; i < N; i++) {
		cout << a[(start_point + i) % N] << ' ';
	}




	return 0;
}

---

문제풀이

---

위 문제에서 중요한 부분은 바로

start_point = (start_point + N - k) % N;

이 문장과,

start_point = (start_point + k) % N;

이 문장이다.

나는 이 문제에서 1번을 입력받았을때 해당 숫자를 x 만큼 늘리는 과정은 어렵지 않다고 생각했다. 입력 받은 수 + x 를 해주고 다시 그 입력받은 수에 넣어주면 되기 때문이다.
하지만, 중요하다고 본게 2번 3번이다. 

나는 일단 전체적으로 수열이 이동하는 것이기때문에, start_point를 잡아주는것이 중요하다고 보았고, 배열의 start_point를 0으로 잡고, 계산했다.
먼저 오른쪽으로 이동하는 2번 같은 경우는 첫번째 코드와 같이 작성해보았는데, star_point에서 배열의 길이인 N만큼 더해주고, 입력받은 얼만큼 이동할 것인가?에 대한 k를 빼줬다.(늘어난 길이에서 k를 더해주는것이 아닌 빼주는것은 N만큼 더해줬으니 반대로 생각해주면 된다.) 그 후 N으로 나머지연산을 해주면 원래 배열의 길이로 돌아와 k만큼 이동한 배열을 얻을 수 있다.

다음으로 3번같은경우는 start_point에서 k만큼 더해준 후, (2번의 경우와 반대 ! N을 더해주지 않았으니.) 배열의 길이인 N으로 나머지 연산을 해주면 왼쪽으로 이동한 수열을 도출 해 낼 수 있다.

이 문제를 위 식을 생각하지 않고 배열안에 모든 수를 일일이 옮기려 하면, 시간과 코드가 길어지게 된다.
앞으로 위와 같은 문제 유형을 맞닥트렸을 때 위 식을 잘 생각해 내어 빠른 시간안에 문제를 해결해야겠다고 생각했다.