[백준 BOJ / Python] 25338번 바지 구매 math

문제

주어진 하체 둘레 공식을 참고하여 새로 산 바지를 입었을 때, 둘레가 커서 흘러내리지 않으면서 바닥에 끌리지 않는 바지의 개수를 구하는 문제이다.

 

문제 조건

• 하체 둘레 공식 : $f(x) = max(a(x-b)^2 + c, d)$
• 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸린다.

풀이

바지의 허리 둘레 = u, 길이 = v

< 그림 1 >

• 바지의 하체 둘레가 가장 큰 위치는 $f(x) = max(a(x-b)^2 + c, d)$ 공식에 따라 바닥으로부터 $b$의 위치를 의미한다.
• 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸리기 때문에, 바닥으로부터 길이가 $b$보다 작은 경우는 바지가 짧은 것임을 알 수 있다. 즉, 바지의 길이는 $b$ 길이보다 같거나 커야 한다.
• 바지의 길이가 $v$일 경우, 바지의 허리 둘레는 $v$ 높이의 하체 둘레인 $f(v)$ 와 동일해야 바지가 바닥에 끌리지 않는다. 즉, 허리 둘레 $u$가 $f(v)$ 와 같지 않는 경우는 맞지 않는 바지이다.

예제 1

-1 50 10 6
4
10 50
10 52
9 51
9 50

알고리즘

1. 딱맞는 바지를 확인하는 함수를 만든다.
   1. 주어진 공식에 바지의 길이를 입력해 하체 둘레를 구한다.
   2. 하체 둘레와 바지 둘레가 같은지, 만약 같다면 바지가 b보다 긴 길이인지 확인한다.
   3. 맞는 바지면 1, 맞지 않으면 0을 return 한다.
2. n 개의 바지 중 딱맞는 바지의 개수를 더한다.
3. 최종적으로 딱맞는 바지의 개수를 출력한다.

Python 코드

import sys
input = sys.stdin.readline

a,b,c,d = map(int, input().split())

# 맞는 바지인지 확인하는 함수
def fit(u, x):
    fx = max(a * (x - b)**2 + c, d) # 주어진 공식
    # 만약 바지의 허리 둘레와 하체 둘레가 맞는지 
    # 짧아서 흘러내리는 바지는 아닌지 확인
    if fx != u or b > x:
        return 0 # 맞지 않는 바지면 0 return
    return 1     # 맞는 바지면 +1 return
    
n = int(input())
ans = 0 # 맞는 바지 개수 담는 변수
for _ in range(n):
    u,v = map(int, input().split())
    ans += fit(u,v)

print(ans)

 

문제 출처

25338번: 바지 구매