백준 17128 소가 정보섬에 올라온 이유(JAVA)

문제

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

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

코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N, Q, ans = 0;
        int[] A;
        int[] dp;

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        A = new int[N];
        dp = new int[N];

        //품질 점수 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        //dp에 저장
        for (int i = 0; i < N; i++) {
            int temp = 1;
            int a1, a2, a3, a4;

            if (i >= N) a1 = i % (N - 1) - 1;
            else a1 = i;

            if (i + 1 >= N) a2 = (i + 1) % (N - 1) - 1;
            else a2 = i + 1;

            if (i + 2 >= N) a3 = (i + 2) % (N - 1) - 1;
            else a3 = i + 2;

            if (i + 3 >= N) a4 = (i + 3) % (N - 1) - 1;
            else a4 = i + 3;

            temp *= A[a1];
            temp *= A[a2];
            temp *= A[a3];
            temp *= A[a4];
            dp[i] += temp;
            ans += temp;
        }

        //Q번만큼 재계산
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < Q; i++) {
            int qi = Integer.parseInt(st.nextToken());
            if(--qi == -1)
                qi = N-1;
            for (int j = 0; j < 4; j++) {
                dp[qi] = -dp[qi];
                ans += 2*dp[qi];
                if(--qi == -1){
                    qi = N-1;
                }
            }
            sb.append(ans + "\\n");
        }
        System.out.println(sb.toString());
    }

}

풀이

 높은 정답률과 단순 반복으로 쉽게 접근하였지만 이중for문으로 처리할 경우 20만*20만으로 제한시간인 2초를 아득히 넘어서기 때문에 다른 방식을 구현해야한다. 그래서 dp를 생각해보기도 하였지만 결국 구현을 하다보니 이중 for문과 다를게 없는 코드가 되었다. 그렇기에 다른 사람의 코드를 참고하였고 이해하는데 역시 시간이 조금 걸렸던것 같다.

풀이의 개요는 다음과 같다. 먼저 소의 품질 점수를 변경하지 않고 4개의 연속된 s를 구해서 따로 저장해둔다. 그리고 해당 s의 값을 전부 더해서 저장해둔다.

 

 그리고 핵심은 -1로 바꾼 품질 점수가 포함된 s의 값의 부호를 전부 바꿔서 두번더한다(s1 + s2 + s3 + s4에서 만약 s2에 속하는 소의 품질 점수가 바뀌었다면 s1 + s2 + s3 + s4 - s2 -s2를 하면 결과적으로 s1 - s2 + s3 + s4가 되기 때문)또한 부호가 한번 바뀌면 바뀌는 값은 전부 4개 이기 때문 4번 반복해준다.