백준 14655 - 욱제는 도박쟁이야!! (자바 - 그리디)

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

14655번: 욱제는 도박쟁이야!!

 

* 문제 요약

동전 뒤집기 게임을 한다.

동전 양면에는 절댓값이 같고, 부호가 다른 정수가 한면에 하나씩 쓰여있다.

여기서 동전끼리는 쓰인 수의 절댓값이 다를 수 있다.

한 플레이어당 두 번의 라운드가 주어지며 모든 라운드는 같은 동전으로 진행된다.

딜러는 각 라운드마다 N 개의 동전을 임의로 섞고 이를 일렬로 배열한다. 이때, 동전의 앞뒤 방향도 바뀔 수 있다.

 

첫번째 라운드에서는 동전에 표시된 값들의 합이 최대가 되도록 뒤집어야 하고, 두번째 라운드에서는 동전에 표시된 값들의 합이 최소가 되도록 뒤집어야 한다.

(첫번째 라운드 동전 값의 합) - (두번째 라운드 동전 값의 합) 이 해당 플레이어가 게임에서 획득한 점수이고, 이 점수가 최대가 되는 플레이어가 바로 게임의 승자가 된다.

 

항상 연속된 3개의 동전을 뒤집되, 동전 배열의 양 끝의 동전 하나만 뒤집거나 양 끝의 동전 2개만 뒤집는 것도 가능하며 동전을 뒤집는 횟수 제한은 없다.

 

항상 최고점의 점수를 얻는다고 할 때, 각 입력에 대해서 얻을 수 있는 최고 점수를 구하시오

 

* 입력

첫째줄에 동전의 수 N 이 주어진다.(1 <= N <= 10000)

둘째줄에 첫 번째 라운드의 N 개 동전의 배열이 주어진다.

셋째줄에 두 번째 라운드의 N 개 동전의 배열이 주어진다.

동전에 적히는 수는 절댓값 10000 이하의 정수이다.

 

* 출력

각 입력에 대해서 획득할 수 있는 최고 점수를 출력하라.

 

* 예시

 

* 해결 과정

각 라운드에서 입력받은 동전 배열을 처음부터 순서대로 탐색한다.

매 반복마다 현재 인덱스 값이 양수인지 음수인지 확인하고 각 라운드의 조건에 맞게끔 동전을 뒤집어준다.

첫번째 라운드의 경우 동전에 표시된 값들의 합이 최대가 되려면 배열의 동전들이 최대한 양수가 되게끔 뒤집어 줘야 한다.

- 현재 탐색하고 있는 인덱스의 값이 양수인 경우 건너뛴다.

- 현재 탐색하고 있는 인덱스의 값이 음수인 경우 내부에서 추가로 반복문을 동작시켜, 현재 인덱스를 포함해서 연달아 최대 3개의 동전 값에 -1 을 곱해준다.

- 연달아서 최대 3개의 동전값에 -1을 곱해주려던 도중 배열의 끝에 도달하면 내부 반복문을 종료시키고 다음 인덱스 탐색으로 넘어간다.

 

두번째 라운드의 경우 동전에 표시된 값들의 합이 최소가 되려면 배열의 동전들이 최대한 음수가 되게끔 뒤집어 줘야 한다.

- 현재 탐색하고 있는 인덱스의 값이 음수인 경우 건너뛴다.

- 현재 탐색하고 있는 인덱스의 값이 양수인 경우 내부에서 추가로 반복문을 동작시켜 현재 인덱스를 포함해서 연달아 최대 3개의 동전 값에 -1을 곱해준다.

- 연달아서 최대 3개의 동전 값에 -1을 곱해주려던 도중 배열의 끝에 도달하면 내부 반복문을 종료시키고 다음 인덱스 탐색으로 넘어간다.

 

정리하자면 아래와 같다.

- 첫번째 라운드라서 양수를 최대한 만들어야 하므로 탐색 때 음수가 발견되면 그 뒤의 숫자가 양수이든 음수이든 상관없이 배열의 끝에 도달한 것이 아닌 한 최대 3개까지 동전을 모두 뒤집기

- 두번째 라운드라서 음수를 최대한 만들어야 하므로 탐색 때 양수가 발견되면 그 뒤의 숫자가 양수이든 음수이든 상관없이 배열의 끝에 도달한 것이 아닌 한 최대 3개까지 동전을 모두 뒤집기

 

결과로서 첫번째 라운드에서는 모든 동전들이 양수 쪽 표면으로 뒤집히게 되고

두번째 라운드에서는 모든 동전들이 음수쪽 표면으로 뒤집히게 된다.

 

각 라운드 별로 동전들을 조건에 맞게 뒤집어준 다음 합산한 값들을 서로 더해주면 정답을 출력할 수 있다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        // 첫번째 라운드
        String[] input = br.readLine().split(" ");
        int[] firstArray = new int[n];
        for (int i = 0; i < n; i++) {
            firstArray[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < n; i++) {
            if (firstArray[i] < 0) {
                int count = 0;
                while (count < 3) {
                    if (i + count > n - 1)
                        break;
                    else {
                        firstArray[i + count] *= -1;
                        count++;
                    }
                }
            }
        }

        // 두번째 라운드
        input = br.readLine().split(" ");
        int[] secondArray = new int[n];
        for (int i = 0; i < n; i++) {
            secondArray[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < n; i++) {
            if (secondArray[i] > 0) {
                int count = 0;
                while (count < 3) {
                    if (i + count > n - 1)
                        break;
                    else {
                        secondArray[i + count] *= -1;
                        count++;
                    }
                }
            }
        }

        // 합산
        int number1 = Arrays.stream(firstArray).sum();
        int number2 = Arrays.stream(secondArray).sum() * -1;
        bw.write((number1 + number2) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

매 반복마다 각 인덱스에 대해 자신의 다음번 인덱스가 무엇이냐에 관계없이 현재 인덱스가 양수이냐 음수이냐에 따라 최적화된 로직이 독립적으로 동작하므로 그리디 알고리즘 문제에 해당된다.