2025 한국정보올림피아드(KOI) 1차 대회 2교시 중등부
한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.
1. 직각이등변삼각형 (초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 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.
ⓒ (3, 1)
밑 변과 떨어진 거리가 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 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.
ⓒ (0, -1)
윗 변과 떨어진 거리가 5입니다.
윗 변 왼쪽 끝 점 x좌표가 0 - 5 = -5 또는 더 왼쪽,
윗 변 오른쪽 끝 점 x좌표가 0 + 5 = 5 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.
ⓓ (4, -1)
윗 변과 떨어진 거리가 5입니다.
윗 변 왼쪽 끝 점 x좌표가 4 - 5 = -1 또는 더 왼쪽,
윗 변 오른쪽 끝 점 x좌표가 4 + 5 = 9 또는 더 오른쪽이라면 이 점은 삼각형 경계 또는 내부에 존재합니다.
네 점을 모두 확인했을 때 빗변이 가장 짧으면서 삼각형이 모든 점을 포함하려면
왼쪽 끝 점 x좌표는 ⓒ 케이스의 -5, 가장 오른쪽 끝 점 x좌표는 ⓓ 케이스의 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)만큼 좌우를 확장했을 때 가장 왼쪽과 오른쪽 찾기
- 두 결과 중 더 짧은 값을 선택하여 출력
📊 정답률
2. 부산 관광 (중1/고1)
추가 예정
3. 건초 더미 (중3)
추가 예정