[백준/BOJ]14655. 욱제는 도박쟁이야!! [Bronze1]
- 욱제는 도박쟁이야!!
문제출처 : 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; }
Author And Source
이 문제에 관하여([백준/BOJ]14655. 욱제는 도박쟁이야!! [Bronze1]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jychan99/14655.-욱제는-도박쟁이야-Bronze1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)