[백준/BOJ]14655. 욱제는 도박쟁이야!! [Bronze1]

14655. 욱제는 도박쟁이야!!

문제출처 : https://www.acmicpc.net/problem/14655

이 문제를 풀면서 진짜 여러번 시도했는데, 결국 내힘으로는 못풀었다.
블로그를 찾아서 풀이를 봤는데,
『욱제는 연속한 3개의 동전을 뒤집지 않으면 이길 수 없다고 생각하기 때문에 실패하는 경우 없이 항상 연속한 3개의 동전만 뒤집는다. 동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다.』
에 정답이 있었다.
연속한 3개의 동전을 뒤집을 수 있고, 양쪽 동전들만 뒤집을 수도 있다는 말은
모든동전을 2번이상뒤집을수 있다는거고, 궁극적으로 모두 양수, 모두 음수로 만들 수 있다는 것이다.
그래서 첫번째 라운드에서는 모두 양수로, 두번째 라운드에서는 모두 음수로 만들어주면 최대 점수를 딸 수 있는것이다.
이것이 바로 탐욕알고리즘이라는 것이였다...
이때까지는 그냥 문제풀고, 더쉬운방법이 있었네~ 했었는데, 이 풀이를 보니까 확 와닿았다.
문제의 전체를 보면서 어떤 다른방법, 더 쉬운 최적의 경로를 찾는 시각을 키워야겠다는 생각을 했다.

code

#include <stdio.h>
#include <stdlib.h> // 절대값으로 바꿔주는 abs()함수를 쓰기위한 헤더
int main()
{
	int N, i, score = 0;
	int coin;
	scanf("%d", &N); //코인갯수를 입력받는다
	for (i = 0; i < N; i++)
	{
		scanf("%d",&coin);
		if (coin < 0)
			coin = abs(coin); //절댓값으로 만들어주는 함수 abs()
		score += coin;
	}
	scanf("\n"); //공백
	for (i = 0; i < N; i++)
	{
		scanf("%d", &coin);
		if (coin < 0)
			coin = abs(coin);
		score += coin;
	}
	printf("%d", score);
	return 0;
}