[백준/13352] 석양이 진다... (Python)

Problem : https://www.acmicpc.net/problem/13352

13352번: 석양이 진다...

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:30:14

 

---

 

문제 설명

 

 

피스키퍼 리볼버로 무장한 무법자 제시 맥크리는 자신만의 방식으로 정의를 실현한다.

그랬던 맥크리가 새로운 무기를 손에 넣었다. 새로운 무기는 멈추지 않는 총알으로 한번 발사되면 적을 뚫고 지나간다. 즉, 인공지능 상대들처럼 한 줄로 서서 달려오는 적들은 맥크리의 새로운 무기를 한번만 쏘면 죽게 된다.

새 무기로 신나게 적들을 쏴죽이던 맥크리는 총알이 두개밖에 남지 않았다는 사실을 깨닫고 절망하기 시작했다. 그런 가운데 구원의 목소리가 들려왔으니....

"아무도 내게서 숨진 못 해."

이제 맥크리는 적들의 위치를 안다. 남은 총알은 두 발, 먼저 구른 뒤에 적들을 향해 총을 한번 쏘고 다시 한 번 구른 뒤 마지막으로 한번 더 쏜다. 이 계획이 성공하면 맥크리는 모든 적을 섬멸할 수 있다. 이 작전은 과연 성공할 수 있을까?

맥크리는 구르는 속도가 아주 빨라서 순식간에 어디로든 굴러갈 수 있다.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에는 적의 수 N이 입력된다. (1 ≤ N ≤ 100,000)

이어서 입력되는 N개의 줄에는 두개의 정수 Xi  Yi 가 입력된다. i번째 적의 위치 좌표는 (Xi, Yi)이다. (−10^9 ≤ Xi, Yi ≤ 10^9) 단, 같은 위치에 두 명의 적이 있을수는 없다.

작전 지역은 평지이므로 높이는 신경쓰지 않아도 된다.

 

출력

 

맥크리는 총알 두발로 적들을 없애려 한다. 이 계획의 성공 여부를 출력하라.
성공할 시 "success"를 실패할 경우 "failure"를 출력하면 된다.

 

입력 예시

 

6
-1 0
0 0
1 0
-1 1
0 2
1 1

 

출력 예시

 

failure

 

 

---

 

풀이

 

우선 다음과 같은 접근법을 생각해 볼 수 있다.

 

• success case에서는, 두 선분으로 모든 점들을 포함할 수 있다.
• 즉 두 점을 뽑고, 두 점과 동일한 선분 내에 위치한 모든 점들을 찾는다.
  • CCW 방식을 사용했을 때, 동일 선분 내라면 CCW값이 0이 된다.
• 앞선 search 과정에서 뽑히지 않은 점들에 대하여 같은 방식으로 동일 선분 내의 모든 점들을 찾는다.
• 만약 두 번의 search 과정에서 남은 점이 존재한다면, 두 선분으로 모든 점을 포함할 수 없다. 즉 failure를 출력한다. 남은 점이 없다면 두 선분으로 모든 점을 포함시켰으므로 success를 출력한다.

 

하지만 여지없이 wa를 받았다. 너무 억울해서(?) 문제 분류를 보고 그 해답을 바로 찾아낼 수 있었다.

 

우리가 search 초반에 두 점을 뽑을 때, 두 점이 다른 선분 내에 위치할 경우를 생각할 수 있다.

...이런 식으로

 

 

이러한 경우, search 시 최대 3개의 선분을 찾아내 버리므로 failure로 분류되어 버린다.

 

다시 돌아가서, 우리가 임의의 두 점을 뽑을 때, 두 점이 최적화된 한 직선 내에 뽑힐 확률을 생각하면 최소 0.5라는 사실을 알 수 있다. 즉 좌표를 랜덤하게 섞고, 그 랜덤한 좌표 중 두 점을 뽑는 과정을 반복한다. 한 번이라도 success라면 두 직선으로 잇는 것이 가능하다. 이 랜덤 횟수가 10일 경우, 실패할 확률(두 점을 모두 이을 수 있음에도 불구하고 모든 추출이 실패할 경우)는 1 - 0.5^10으로, 매우 적다. 즉 무작위화가 포인트였다.

 

풀이 코드

import random
import sys
input = sys.stdin.readline

N = int(input())
coord_list = [tuple(map(int, input().split())) for _ in range(N)]
if N < 4 :
  print("success")
  exit()
def ccw(a, b, c) :
  return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1]) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])

def search(coord, ret) :
  next_coord = []
  for _coord in coord :
    if ccw(ret[-2], ret[-1], _coord) != 0 :
      next_coord.append(_coord)
  return next_coord

flg = False
for _ in range(10) :
  tmp = coord_list[:]
  for i in range(2) :
    ret = random.sample(tmp, 2)
    tmp = search(tmp, ret)
    if len(tmp) < 2-i :
      flg = True
      break
  if flg :
    break
print("success" if flg else "failure")

풀이 완료!

 

p.s. 밑의 len(tmp) < 2-i를 붙인 이유는 random.sample의 k 인자 때문이다. k인자값이 population 값보다 크다면 valueerror를 일으키므로, 첫 번째 순회 후 남은 좌표 개수가 2 미만, 두 번째 순회 후 남은 좌표 개수가 1 미만일 경우 success하도록 설정하였다.

p.s.2. N < 4 이라면 무조건 가능하다.

p.s.3. 이제는 맥크리라 부르지 못하는 그 캐릭터에게 다시금 깊은 애도를 표한다...