문제 이해 단계
입력으로 소의 수 N과 횟수 Q가 주어진다.
그 아랫줄은 소에 붙어있는 스티커의 정보가 n개 들어온다.
그리고 마지막줄에는 스티커를 바꿀 소의 번호를 순서대로 입력한다.
소는 원형을 둥글게 서있고, 소를 선택하면 해당 소의 붙어있는 번호의 -1을 곱한다.
여기서 하는 연산은 모든 가능한 경우의 수에
대해 연속하는 4개의 소의 번호에 적혀있는 수를 곱한다.
그리고 곱한 수들을 모두 더한다.
출력하는 것은 번호를 바꿀 때마다 달라지는 연산의 결과이다.
문제 접근 단계
일단 이 문제에서 핵심이 되는 부분은 4개의 연속된 수라는 점과
소들이 원형 배치되어 있다는 것이다.
위에서 만든 연산식을 계산하는 코드를 만드는 것은 그렇게 어려운 일이 아니다.
중요한 것은 소가 원형 배치 되어있기 때문에,
첫 번째 소와 마지막 소가 연속이라는 것을 구현해야 하는 점이다.
그리고 N이 최대 200,000이고, 품질 점수가 최대 10이기 때문에
200,000 * 10 * 10^4 = 10^10이다.
즉, int형을 초과하기 때문에 범위에 대해서 신경 써야 한다.
또한 소의 개수 N이 최대 200,000이기 때문에 연산의 개수가 꽤 많다.
시간초과도 생각해줘야 한다.
최대한 빠르게 연산
처음에는 그냥 소의 번호가 바뀌면, 전체적인 연산을 다시 해주려고 했다.
그런데 소의 수가 많으면,
쓸데없는 연산이 너무 많아짐으로 시간초과가 날 확률이 커진다.
그래서 다른 방법이 필요했다.
내가 사용한 방법은 4개씩 연속된다는 점에서 가져왔다.
소가 N마리일 때 각 곱연산은 N번 진행된다.
그중에서 1개가 바뀌면 영향을 받는 곱연산은 4개밖에 없다.
나머지는 영향을 받지 않는다.
방식은 스티커를 바꾸면 영향을 받지 않은
나머지 곱연산은 그대로 둔 채, 영향받은 4개의 연산만 계산해 주는 것이다.
그런데 생각해 보면 이미 곱연산을 통해 값을 구해놨다면
새로운 연산을 할 필요도 없다.
왜냐하면 선택된 소의 스티커에 -1만 곱하는 것이기 때문이다.
그렇기 때문에 그냥 해당 곱연산 값에 -1만 곱해주면 된다.
즉, 영향받는 4가지 곱연산값에 각각 -1을 곱해주면 된다.
위 방식을 통해 불필요한 연산을 줄일 수 있다.
그리고 출력해야 하는 답도 영향받은 곱연산을 가지고 도출해 낼 수 있다.
알고리즘은 다음과 같다.
1.
기본 상태(스티커를 건드리지 않은 상태) 일 때의
각 배열의 곱연산값을 저장해 준다.
ex) sum [3] = 40 : 3번째 소의 번호가 가장 앞에 있을 때의 곱연산의 값은 40이다.
예를 들어 3번째 소의 스티커가 3이라고 하면
3*2*1*4같이 3번째 소의 스티커 번호가 가장 앞에 나와있는 것
2.
곱연산을 모두 더한 값을 저장해 둔다.
이를 Total이라고 부르겠다.
3.
스티커를 바꾸면 해당 번호에 영향을 받은 번호는
Total 계산에 들어갈 수 없기 때문에 일단 빼준다.
Total - (영향을 받은 곱연산(sum 배열))
4. 영향을 받은 곱연산 배열에 -1을 곱해서 total에 더해준다.
이렇게 하면 total이 우리가 원하는 답이 된다.
이제 이를 알고리즘으로 구현만 하면 된다.
문제 구현 단계
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N,Q; // N : 소의 수. Q : 횟수
scanf("%d %d",&N,&Q);
vector<int> cow(N); // 스티커 정보를 인덱스(번호순)으로 담음
vector<int> joke(Q); // 스티커를 바꿀 소의 순서
for(int i = 0; i < N; i++) scanf("%d",&cow[i]);
for(int i = 0; i < Q; i++) scanf("%d",&joke[i]);
vector<long long> sum(N); // 곱연산 배열
long long total = 0; // total
// 기본 상태일때의 곱연산 배열을 초기화
for(int i = 0; i < N; i++){
long long v = 1;
for(int j = i; j < i + 4; j++) v *= cow[j%cow.size()];
sum[i] = v;
total += sum[i];
}
// int를 초과하기 때문에 long long으로 받아야함
for(int i = 0; i < joke.size(); i++){
int k = joke[i]-1; // 인덱스는 0부터 시작하기 때문
// sum[a]가 a가 맨 앞에 있을 경우이기 때문에
// a가 포함되어 있으려면 뒤로 이동해야함
for(int j = k; j > k - 4; j--) {
// 음수로 될 경우 이를 갱신해줘야함
if(j < 0) {
total -= sum[cow.size() + j];
sum[cow.size() + j] *= -1;
total += sum[cow.size() + j];
}
else{
total -= sum[j];
sum[j] *= -1;
total += sum[j];
}
}
printf("%lld\n",total);
}
}전체적으로 구현한 코드이다.
코드 자체는 그렇게 어렵지는 않은데 중요하게 봐야 할 점은
sum배열에 곱연산을 담는 것과 그 아래에 연속된 4개의 소를 보는 것이다.
소가 원형으로 둘러싸여 있기 때문에
0번 소(첫 번째 소) 이전에는 마지막 소가 된다.
이를 코드적으로 해석해줘야 한다.
그 해석해 준 것이 if(j < 0) 일 때이고,
그 위를 보면 for(int j = k; j > k - 4; j--)가 있는데 이게 중요하다.
선택된 소에서 연속을 앞이 아닌 뒤로 가는 것이다.
이렇게 해주는 이유는 내가 sum [a]를 "a번째 소가 가장 앞에 있을 때의 연산"
이라고 해줬기 때문에 앞으로 가버리면 a번째 소는 더 이상 포함이 안된다.
그렇기 때문에 뒤로 4번을 가줘야 하는 것이다.
나머지는 위에서 설명한 그대로
영향받은 sum배열에 -1을 곱하고 더하고 빼주고 뭐 그런 것인데,
나머지는 코드를 보면 된다.
시행착오
이상하게 오래 걸렸다.
그렇게 오래 걸릴 문제는 아니었던 것 같은데,
아직 실버 문제라도 쉽게 쉽게 풀어낼 정도는 아닌가 보다.
처음에는 일일이 계산했다가 시간초과가 뜨고,
그다음에는 모듈러 연산을 썼다가
마이너스로 시작될 때 값이 이상하게 돼서 그냥 저런 식으로 표현해 줬다.
모듈러 연산은 그냥 0 이상인게 보장될 때만 사용해야겠다.