[백준] 17128번 - 소가 정보섬에 올라온 이유 [Java]

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

 

[백준] 17128번 - 소가 정보섬에 올라온 이유 [Java]

[백준] 17128번 - 소가 정보섬에 올라온 이유 [Java]

---

1.  아이디어

 

다이나믹 프로그래밍을 활용해 합을 미리 구하고 변경하는 방식으로 해결했다.

---

2. 문제풀이

 

주어진 소들에 대해 4마리의 스티커의 곱을 번호가 작은 소와 매핑시킨 dp 배열을 만든 후 dp 배열의 합을 구했다. 이후 변경할 소의 번호가 주어지면 dp 배열에서 변경해야하는 4마리 점수 4 그룹을 소의 번호로 바로 알 수 있다. 변경은 부호만 바꾸면 되며 부호 변경 후 이전에 구한 dp 배열의 합에서 변경치를 고려해서 수정해주면 된다. 이때 부호가 변경되는 실제 합은 2배 차이가 나게 된다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N];
        dp[0] = arr[0] * arr[1] * arr[2] * arr[3];

        int sum = dp[0];
        for (int i = 1; i < N; i++) {
            dp[i] = dp[i - 1] / arr[i - 1] * arr[(i + 3) % N];
            sum += dp[i];
        }

        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int q = Integer.parseInt(st.nextToken());

            int idx1 = (q - 4 + N) % N;
            int idx2 = (q - 3 + N) % N;
            int idx3 = (q - 2 + N) % N;
            int idx4 = (q - 1 + N) % N;

            dp[idx1] *= -1;
            dp[idx2] *= -1;
            dp[idx3] *= -1;
            dp[idx4] *= -1;

            sum += dp[idx1] * 2;
            sum += dp[idx2] * 2;
            sum += dp[idx3] * 2;
            sum += dp[idx4] * 2;

            sb.append(sum).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기