[BOJ/C++] 욱제는 도박쟁이야!! - 14655번 / CPP풀이

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

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

그리디 알고리즘 문제이다.

 

문제에서 이해가 잘 안되는 문장이 있는데

항상 연속한 3개의 동전만 뒤집는다고 해놓고 저게 뭔말인지........

간단하게 말하면 3개의 인덱스를 동시에 뒤집는 것이 아니라 배열 맨 처음 or 마지막 2개씩 혹은 1개씩 뒤집는 행위가 가능하다는 것이다.

끝에서 두개를 뒤집거나 끝에서 하나를 뒤집는 방식이 가능함!

 

풀이는 두가지가 있는데 먼저 첫번째 풀이

첫 배열의 모든 원소는 +로 만들고, 두 번째 배열의 모든 원소는 -로 만든 뒤 각 배열의 차를 구하는 방식!

 

1. 모든 배열의 원소를 +로 만들거나 -로 만드는 방법

어떻게 모든 배열의 원소를 하나의 부호로 맞출 수 있을까?

모든 배열을 +로 만드는 예시를 보자.

답은 그냥 0번 인덱스부터 시작하여 -인 배열의 원소에 -1을 곱해주는 것이다.

 

맨 위 검은색이 초기 배열 상태

노란색 부분이 3개씩 바뀌는 부분이다.

 

2번째 배열의 합을 최솟값으로 만드는 로직(모든 원소 음수로)은 반대로 짜면 된다.

 

아무튼 음수를 양수로, 양수를 음수로 바꾸는 기능을 열심히 구현을 하고 있는데 문득 이상한 점을 깨달았다.

어짜피 모든 배열이 +로 바뀌거나 -로 바뀌는거라면 숫자를 입력받을 때 모두 양수로 바꾸고 그 두개만 더해주면 되잖아?

 

 

태그는 그리디 알고리즘뿐 아니라 애드 혹 문제여도 어울렸을 것 같다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    int total = 0;

    for (int i = 0; i < n; i++) {
        int c; cin >> c;
        // 음수라면 양수로 바꿔서 total에 더해줌
        if (c < 0) {
            total += (-1 * c);
        }
        else
            total += c;
    }
    for (int i = 0; i < n; i++) {
        int c; cin >> c;
        if (c < 0) {
            total += (-1 * c);
        }
        else
            total += c;
    }

    cout << total;
}