[그리디 알고리즘 Lv.02] 14655번 욱제는 도박쟁이야!! (Python)

1. 문제
    14655번 욱제는 도박쟁이야!!
    (https://www.acmicpc.net/problem/14655)

 

욱제는 라스베이거스에서 유명한 베팅꾼이다. 어찌나 게임을 잘 하는지 ‘제2의 홍진호’라는 별명이 붙었을 정도다. 어찌나 게임을 잘 하는지 ‘제2의 홍진호’라는 별명이 붙었을 정도다.

욱제가 주로 하는 게임은 아주 단순하고, 친숙한 게임이다. 바로 동전 뒤집기 게임이다. 이 게임에 쓰이는 동전의 양면에는 절댓값이 같고 부호가 다른 정수가 한 면에 하나씩 쓰여 있다. (단, 동전끼리는 쓰인 수의 절댓값이 다를 수 있다) 한 플레이어 당 두 번의 라운드가 주어진다. 모든 라운드는 같은 동전으로 진행되며, 딜러는 각 라운드마다 N개의 동전을 임의로 섞고 이를 일렬로 배열한다. 이때, 동전의 앞뒤 방향도 바뀔 수 있다. 첫 번째 라운드에서는 동전에 표시된 값들의 합이 최대가 되도록 뒤집어야 하고, 두 번째 라운드에서는 동전에 표시된 값들의 합이 최소가 되도록 뒤집어야 한다. (첫 번째 라운드 동전 값의 합) - (두 번째 라운드 동전 값의 합)이 해당 플레이어가 게임에서 획득한 점수이고, 이 점수가 최대가 되는 플레이어가 바로 게임의 승자가 된다.

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

(!) 너, 강해 보이는군. 나와 승부를 겨루자! 띠리링띠리링디리ㅣ리리ㅣ링~ 앗! 심술쟁이 해커 임준오(동탄 주민)이 승부를 걸어왔다!

욱제는 이번 게임에서 얼마의 점수를 획득하게 될까? 욱제는 최고의 베팅꾼이기 때문에 항상 게임에서 획득할 수 있는 최고의 점수를 얻는다는 사실은 자명하다.

 

 

2. 문제 포인트

• 동전 개수 랜덤
• 3개씩 (양 끝은 1개, 2개씩) 무제한으로 뒤집을 수 있음
• 1라운드 최대 합계, 2라운드 최소 합계로 점수 계산
• 최솟값은 절대값에 '-1'을 곱하면 최솟 합계가 됨

반응형

 

3. 접근법

• 3개씩 (양 끝은 1개, 2개씩) 무제한으로 뒤집을 수 있음
  = 결과적으로 모든 숫자를 양수, 또는 음수로 만들 수 있음
  

  

• 전체 숫자의 절대값을 계산하여 합계를 구하면 해결 가능

 

 

 

4. 결과 코드

import sys

a = sys.stdin.readline()

r1 = list(map(int, sys.stdin.readline().split()))
r2 = list(map(int, sys.stdin.readline().split()))

# 1라운드 최대값 구하기
## 모든 숫자가 양수가 되면 최대값 = 절대값들의 총합
r1 = sum(list(map(abs, r1)))

# 2라운드 최솟값 구하기
## 모든 숫자가 음수가 되면 최대값 = 절대값들의 총합 * -1
r2 = sum(list(map(abs, r2)))

print(r1 + r2)

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