17128번 소가 정보섬에 올라온 이유

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

처음에 2중 for문으로 한 번 제출해봤는데 역시나 200,000라서 시간 초과가 떴다.

시간 초과 후 2중 for문을 안 쓰려고 했다.

예제를 활용하여 풀었다.

핵심은 vector와 배열의 인덱스를 활용하는 것이다.

total 변수도 활용한다.

숫자는 배열의 인덱스

sum	A
1	1 2 3 4
2	2 3 4 5
3	3 4 5 6
4	4 5 6 7
5	5 6 7 8
6	6 7 8 1
7	7 8 1 2
8	8 12 3 4

숫자는 인덱스

떼어낼 인덱스(A 배열)	떼어낼 인덱스를 포함하는 sum 배열
1	1 6 7 8
2	2 1 8 7
3	3 2 1 8
4	4 3 2 1
5	5 4 3 2

규칙 : 떼어낼 인덱스를 k라고 하면, k--씩 감소하여 idx vector에 넣는다. 범위만 주의.

예시) 

sum[1] = ABC

sum[2] = DEF

total = sum[1] + sum[2] = ABC + DEF

B를 -B로 바꾸려면, total = total + 2 * (-1) * sum[1] 이다.(-ABC + DEF)

2개의 코드를 올리겠다.

시간 초과 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int sum[200200] = { 0, }, A[200200] = { 0, }, ans[200200] = { 0, }, N = 0, Q = 0, repeat = 0;
 
vector<int> v;
 
int main(void)
{
    int q = 0;
 
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
    for (int i = 0; i < Q; i++) scanf("%d", &q), v.push_back(q);
 
    repeat = N == 4 ? 4 : N;
 
    int idx = 0;
 
    for (int i = 1; i <= repeat; i++)
    {
        int multi = 1, j = i, r = 4, s = 0;
 
        while (r--)
        {
            multi *= A[j];
 
            ++j;
 
            if (j > N) j %= N;
        }
 
        sum[i] = multi;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        int ans = 0;
 
        for (int j = 1; j <= N; j++)
        {
            int k = j, r = 4;
 
            bool use = false;
 
            while (r--)
            {
                if (k == v.at(i))
                {
                    use = true;
                    sum[j] *= -1;
                    break;
                }
 
                ++k;
 
                if (k > N) k %= N;
            }
 
            ans += sum[j];
        }
 
        printf("%d\n", ans);
    }
 
    return 0;
}

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int sum[200200] = { 0, }, A[200200] = { 0, }, N = 0, Q = 0, repeat = 0;
 
vector<int> v, idx[200200];
 
int main(void)
{
    int q = 0, total = 0;
 
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
    for (int i = 0; i < Q; i++) scanf("%d", &q), v.push_back(q);
    
    repeat = N == 4 ? 4 : N;
 
    for (int i = 1; i <= repeat; i++)
    {
        int multi = 1, j = i, r = 4;
 
        while (r--)
        {
            multi *= A[j];
 
            ++j;
 
            if (j > N) j %= N;
        }
 
        sum[i] = multi;
        
        total += sum[i];
 
        r = 4;
 
        int k = i;
 
        while (r--)
        {
            idx[i].push_back(k);
 
            --k;
 
            if (k == 0) k = N;
        }
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        for (auto a : idx[v.at(i)])
        {
            sum[a] *= -1;
 
            total += 2 * sum[a];
        }
 
        printf("%d\n", total);
    }
    
    return 0;
}