2025 한국정보올림피아드(KOI) 1차 대회 2교시 중등부

한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.

1. 먼 카드 (초1)

추가 예정

2. 직각이등변삼각형 (초2/중1)

제목 링크를 통해 문제를 확인해주세요.

📄 문제 개요

N개의 점이 주어졌을 때,

① N개의 점 모두 직각이등변삼각형의 경계나 내부에 위치(꼭짓점 포함)

② 빗변은 x축과 평행 (빗 변의 두 끝점 y좌표가 같다.)

그 중 빗변의 길이가 가장 짧은 경우의 길이를 구하는 문제입니다.

💡 문제 풀이 개념과 시뮬레이션

직각이등변삼각형은 두 변의 길이가 같고, 그 두 변 사이 각이 직각입니다.

또한 직각이기 때문에 높이(위 그림에서 빨간색)를 그어보면 밑변의 중심에 도착해 밑변의 절반과 길이가 같다는 것도 확인할 수 있습니다.

문제에 주어진 것처럼 N개의 점이 좌표평면에 있을 때, 우리가 고려해봐야할 경우는

① 아래쪽이 빗변, ② 위쪽이 빗변 (문제 조건에서 빗변은 x축과 평행) 2가지입니다.

그러면 먼저 아래쪽이 빗변인 경우를 보겠습니다.

① 아래쪽이 빗변이기 때문에, y축이 가장 작은 점들을 찾아 그 점을 기준으로 가로선을 길게 그어주었습니다.

② 남은 것은 위에 있는 점들인데, 그림에서 밑 변(빗변)과 얼마나 떨어져있는지 높이에 주목해주세요.

직각이등변삼각형이기 때문에 밑 변의 양 끝 점에서 45도 각도를 이루면서 나머지 두 변을 그리게 되고

가로로 왼쪽, 오른쪽이 정확히 한 칸씩 좁혀지게 됩니다.

따라서 어떤 점이 밑 변과 거리 n만큼 떨어져있다면, 최소 그 점 x좌표의 +n, -n만큼의 여유 공간이

밑변에 있어야 한 칸씩 좁혀들어와도 점이 경계나 내부에 존재할 수 있다는 사실을 알 수 있습니다.

이제 남은 세 점을 모두 살펴보겠습니다.

* 밑 변의 y좌표 : -1

ⓐ (-1, 2)

밑 변과 떨어진 거리가 3입니다.

밑 변 왼쪽 끝 점 x좌표가 -1 - 3 = -4 또는 더 왼쪽,

밑 변 오른쪽 끝 점 x좌표가 -1 + 3 = 2 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

ⓑ (2, 4)

밑 변과 떨어진 거리가 5입니다.

밑 변 왼쪽 끝 점 x좌표가 2 - 5 = -3 또는 더 왼쪽,

밑 변 오른쪽 끝 점 x좌표가 2 + 5 = 7 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

밑 변과 떨어진 거리가 2입니다.

밑 변 왼쪽 끝 점 x좌표가 3 - 2 = 1 또는 더 왼쪽,

밑 변 오른쪽 끝 점 x좌표가 3 + 2 = 5 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

세 점을 모두 확인했을 때 빗변이 가장 짧으면서 삼각형이 모든 점을 포함하려면

왼쪽 끝 점 x좌표는 ⓐ 케이스의 -4, 가장 오른쪽 끝 점 x좌표는 ⓑ 케이스의 7이 되는 것을 확인했습니다.

따라서 이 경우 빗변의 최소 길이는 7 - (-4) = 11이 됩니다.

같은 방법으로 위쪽이 빗변인 경우를 보겠습니다.

위쪽이 빗변이기 때문에 주어진 점들 중 가장 y좌표가 큰 점을 찾아 가로선을 길게 그어주었습니다.

* 윗 변의 y좌표 : 4

ⓐ (-1, 2)

윗 변과 떨어진 거리가 2입니다.

윗 변 왼쪽 끝 점 x좌표가 -1 - 2 = -3 또는 더 왼쪽,

윗 변 오른쪽 끝 점 x좌표가 -1 + 2 = 1 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

ⓑ (3, 1)

윗 변과 떨어진 거리가 3입니다.

윗 변 왼쪽 끝 점 x좌표가 3 - 3 = 0 또는 더 왼쪽,

윗 변 오른쪽 끝 점 x좌표가 3 + 3 = 6 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

윗 변과 떨어진 거리가 5입니다.

윗 변 왼쪽 끝 점 x좌표가 0 - 5 = -5 또는 더 왼쪽,

윗 변 오른쪽 끝 점 x좌표가 0 + 5 = 5 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

ⓓ (4, -1)

윗 변과 떨어진 거리가 5입니다.

윗 변 왼쪽 끝 점 x좌표가 4 - 5 = -1 또는 더 왼쪽,

윗 변 오른쪽 끝 점 x좌표가 4 + 5 = 9 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.

네 점을 모두 확인했을 때 빗변이 가장 짧으면서 삼각형이 모든 점을 포함하려면

따라서 이 경우 빗변의 최소 길이는 9 - (-5) = 14가 됩니다.

아래쪽이 빗변일 때 최소 길이는 11, 위쪽이 빗변일 때 최소 길이는 14이기 때문에 둘 중 더 짧은 11이 정답이 됩니다.

💻 코드 구현

n = int(input())
arr = []
for i in range(n):
    arr.append(tuple(map(int, input().split())))

max_y = float('-inf')
min_y = float('inf')

for i in arr: # 밑 변, 윗 변 y좌표 찾기
    y = i[1]
    min_y = min(min_y, y)
    max_y = max(max_y, y)

# 아래쪽이 빗변
left = float('inf')
right = float('-inf')

for i in arr: # 모든 점을 돌면서 왼쪽 끝, 오른쪽 끝 찾기
    x = i[0]
    y = i[1]
    left = min(left, x - (y - min_y))
    right = max(right, x + (y - min_y))

result = right - left # 빗변 길이(오른쪽 x좌표 - 왼쪽 x좌표)

# 위쪽이 빗변
left = float('inf')
right = float('-inf')

for i in arr: # 모든 점을 돌면서 왼쪽 끝, 오른쪽 끝 찾기
    x = i[0]
    y = i[1]
    left = min(left, x - (max_y - y))
    right = max(right, x + (max_y - y))

# 두 경우 빗변 길이 중 짧은 쪽을 선택
result = min(result, right - left)

print(result)

🧾 코드 설명

min_y : 아래쪽 빗변의 y좌표(모든 점들 중 가장 작은 y좌표)
max_y : 위쪽 빗변의 y좌표(모든 점들 중 가장 큰 y좌표)
아래쪽 빗변 계산 : x좌표에 (y - min_y)만큼 좌우를 확장했을 때 가장 왼쪽과 오른쪽 찾기
위쪽 빗변 계산 : x좌표에 (max_y - y)만큼 좌우를 확장했을 때 가장 왼쪽과 오른쪽 찾기
두 결과 중 더 짧은 값을 선택하여 출력

📊 정답률

3. 허수아비 (초3)

추가 예정