[백준 20206] 파이썬 - 푸앙이가 길을 건너간 이유

https://www.acmicpc.net/problem/20206

20206번: 푸앙이가 길을 건너간 이유

 

 

# 조건

• x축과 y축과 평행한 직사각형 형태로 이루어진 위험지역
• 푸앙이는 직선 상의 경로를 따라 흑석동을 통과
• 푸앙이가 위험 지역을 지나가는지 여부를 알아내어, 해당 지역을 지나가지 못하도록 조치를 취하라
• A,B,C (-10,000 <= A,B <= 10,000, -100,000 <= C <= 100,000)
• Ax + By + C = 0 형태로 표현되는 푸앙이의 직선 상 경로
• 단, A,B 모두 0인 경우 직선의 방정식 아니다
• 직사각형의 테두리들은 x = X1, x = X2, y = Y1, y = Y2 에 해당하는 직선에 포함

 

# 접근 방법

• x의 모서리값에서 y의 값을 구해준다. - y의 절편
• 그 값이 사각형 내부를 지나간다면 lucky 출력, 아니라면 poor 출력
• 내부를 지나간다고 판단하는 방법
  • x1 < x2, y1 < y2이며 우선, 기울기가 0인 경우, 음수인 경우, 양수인 경우로 나눠준다.
• 기울기가 0인 경우 = A, B 중 하나가 0인 경우
  
  • 나머지 x = -(c/a) 가 x의 최소와 최대 사이에 있으면 되며 y도 마찬가지
• 기울기가 음수인 경우 => -(A/B) <0
  • x1에서의 y의 값이 x2에서의 y의 값보다 크다.
  • 따라서, x1에서의 y의 값이 사각형 높이의 최소값 = y1 보다 크고
  • x2에서의 y의 값이 사각형 높이의 최댓값 = y2 보다 작다면
  • 사각형 내부를 지나갈 수 밖에 없다.
• 기울기가 양수인 경우 => -(A/B)>0
  • 음수의 상황과 반대로 x1에서의 y의 값이 x2에서의 y의 값보다 작다.
  • 따라서, x2에서의 y의 값이 y1보다 크고, x1에서의 y의 값이 y2보다 작으면 된다.

 

 

# 브루트 포스를 이용한 시간 초과 코드

import sys  
sys.stdin = open('input.txt')  
  
a,b,c = map(int, input().split())  
  
x1, x2, y1, y2 = map(int, input().split())  
  
expression1 = -(a*x1+c) / b  
expression2 = -(a*x2+c) / b  
result = 'Lucky'  
if 0<=expression1 and 0<=expression2 and expression1 > expression2:  
    while expression2 != expression1:  
        if y1 < expression1 -expression2 < y2:  
            result = 'Poor'  
            break  
        else:  
            expression2 += 0.1  
  
elif 0<=expression1 and 0<=expression2 and expression1 < expression2:  
    while expression2 != expression1:  
        if y1 < expression2 - expression1 < y2:  
            result = 'Poor'  
            break  
        else:  
            expression1 += 0.1  
  
  
elif 0>expression1 and 0>expression2 and abs(expression1) > abs(expression2):  
    while expression2 != expression1:  
        if y1 < expression2 - expression1 < y2:  
            result = 'Poor'  
            break  
        else:  
            expression1 += 0.1  
elif 0>expression1 and 0>expression2 and abs(expression1) < abs(expression2):  
    while expression2 != expression1:  
        if y1 < expression1 - expression2 < y2:  
            result = 'Poor'  
            break  
        else:  
            expression2 += 0.1  
  
elif 0>expression1 and 0 <= expression2:  
    while expression2 != expression1:  
        if expression1 < 0:  
            if y1 < expression2 + expression1 < y2:  
                result = 'Poor'  
                break  
            else:  
                expression1 +=1  
        else:  
            if y1 < expression2 - expression1 < y2:  
                result = 'Poor'  
                break  
            else:  
                expression1 +=1  
  
elif 0<=expression1 and 0>expression2:  
    while expression2 != expression1:  
        if expression2 < 0:  
            if y1 < expression1 + expression2 < y2:  
                result = 'Poor'  
                break  
            else:  
                expression2 += 1  
        else:  
            if y1 < expression1 - expression2 < y2:  
                result = 'Poor'  
                break  
            else:  
                expression2 += 1  
print(result)

 

 

# 네모를 지나는 규칙을 찾아 통과한 코드

import sys  
sys.stdin = open('input.txt')  
A, B, C = map(float, input().split())  
x1, x2, y1, y2 = map(float, input().split())  
  
# x1과 x2에서의 y절편을 구해준다.  
# 이 두점이 최소값과 최댓값 사이에 있다면 네모를 지난다고 할 수 있다.  
dot1 = (-1)*(C+A*x1)/B  
dot2 = (-1)*(C+A*x2)/B  
# 기울기 구해주기  
# 기울기가 0인경우  
result = 'Lucky'  
if A == 0:  
    if y1 < -(C/B) < y2:  
        result = 'Poor'  
  
elif B == 0:  
    if x1 < -(C/A) < x2:  
        result = 'Poor'  
# 기울기가 양수인 경우  
# x2에서의 y이 더 큰 y값  
elif -(A/B) > 0:  
    if y1 < dot2 and dot1 < y2:  
        result = 'Poor'  
# 기울기가 음수인 경우  
# x2에서의 y이 더 작은 y 값  
# 따라서 더 큰 y값을 가진 dot1이 최소값보다 크고, dot2가 최댓값보다 작다면 네모를 지난다.  
else:  
    if y1 < dot1 and dot2 < y2:  
        result = 'Poor'  
print(result)

 

 

• 통과하지 못하더라도 브루트 포스를 통해 먼저 접근을 해주는 것이 중요한 것 같다.
• 그 이후에 줄일 수 있는 조건을 줄이며 최적의 식을 세워주는 것이 아직은 필요한 부분인 것 같다.