백준 14655번 욱제는 도박쟁이야!!

문제 링크입니다: https://www.acmicpc.net/problem/14655

문제의 아래 조건을 이해하는 것이 핵심인 문제였습니다.

"욱제는 연속한 3개의 동전을 뒤집지 않으면 이길 수 없다고 생각하기 때문에 실패하는 경우 없이 항상 연속한 3개의 동전만 뒤집는다. 동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다. 동전을 뒤집는 횟수에 제한은 없다."

결국, 같은 동전을 1번 이상 뒤집을 수 있기 때문에 원하는대로 동전을 배치할 수 있습니다.

따라서 아래와 같이 그리디(Greedy)하게 접근할 수 있습니다.

1 라운드에서는 합이 최대가 되도록 모두 양수로 만들어줍니다.

2 라운드에서는 합이 최소가 되도록 모두 음수로 만들어줍니다.

따라서 (1 라운드 - 2 라운드)는 모든 동전에 적힌 숫자의 절대값들의 합입니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int N;

        cin >> N;

 

        long long sum = 0;

        //1라운드

        for (int i = 0; i < N; i++)

        {

                 int coin;

                 cin >> coin;

 

                 sum += abs(coin);

        }

        //2라운드

        for (int i = 0; i < N; i++)

        {

                 int coin;

                 cin >> coin;

 

                 sum += abs(coin);

        }

        cout << sum << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~