[백준 / 파이썬 /17039] Sleepy Cow Herding (Bronze)

문제

 

• 사용언어: python
• 알고리즘 분류: 수학, 구현
• 난이도: 실버5 (2025.01.11 기준)

 

 

 

 

 

문제 보러가기

[백준] 17039 - Sleepy Cow Herding (Bronze)

 

 

 

 

 

 

문제 정리

• 소 3마리는 서로 다른 위치에 존재한다.
• 소를 이동시켜 연속된 3개의 위치에 배치하고자한다.
• 이동 방법
  • 끝점(최소 숫자 또는 최대 숫자 위치)에 있는 소만 이동할 수 있다.
  • 이동한 뒤에는 더 이상 끝점에 위치해서는 안된다.
    • (= 소와 소 사이로 이동시켜야 한다.)
  • 이동횟수는 몇 칸을 이동했느냐가 아니라, 몇번을 이동했느냐다.
    • (ex) 1번에 3칸 이동 => 이동 횟수 1번으로 카운트

 

✨ 3마리 소의 간격을 모두 1로 만들기 위한 이동횟수를 구하면된다.

 

 

 

 

입출력

• 입력
  • 소 세마리의 위치
• 출력
  • 최소 이동횟수
  • 최대 이동횟수

 

 

 

 

 

 

테스트케이스 이해하기

예제1번을 보면 처음 소의 위치는

각 4, 7, 9이다.

 

최소 이동 횟수는 4 -> 8로 1회이다.

 

최대 이동 횟수는

• 4 -> 6
• 9 -> 5

총 2회다.

 

 

 

 

 

💡 아래에 추가적인 이미지 설명이 있다.

안보고 풀 수 있도록 따로 배치 했다.

 

---

 

풀이

# 3마리 소들의 각 위치
a, b, c = map(int, input().split())

# 각 소 사이의 거리
gap1 = b - a
gap2 = c - b

# 최소 이동 횟수 계산
if gap1 == 2 or gap2 == 2:  # 간격 중 하나가 2라면, 최소 1회 이동으로 연속 가능
    min_moves = 1
elif gap1 == 1 and gap2 == 1:  # 이미 연속된 경우
    min_moves = 0
else:
    min_moves = 2  # 그렇지 않다면 2회 이동 필요

# 최대 이동 횟수 계산
max_moves = max(gap1, gap2) - 1

print(min_moves)
print(max_moves)

 

• 간격 중 하나가 2라면, 멀리 있는 소를 간격 2 사이에 배치시킨다. => 1회
• 이미 연속된 경우 이동하지 않는다. => 0회
• 위의 두 경우가 아니라면
  • 먼저 소 한마리를 이동시켜 간격 2로 만든다.
  • 나머지 소 한마리를 간격 2 사이에 배치시킨다.
  • => 2회

 

 

---

 

그림으로 풀이하기

아래 내용은 위의 코드를 바탕으로 작성했다.

 

 

 

최소 이동횟수 구하기 - 간격중 하나가 2인 경우

간격 2사이에 멀리 있는 소를 배치한다.

👉 총 1회

 

 

 

 

 

 

 

최소 이동횟수 구하기 - 간격이 모두 1인 경우

이미 연속된 위치에 배치되어있다.

👉 이동할 필요 없음, 총 0회

 

 

 

 

 

최소 이동횟수 구하기 - 위의 두 경우가 아닌 경우

0) 이 경우에는 가운데 소를 기준으로 

1) 2칸 거리를 둔 위치에 양쪽 끝에 있는 소중 한마리를 배치한다.

2) 이동 안했던 반대편 소를 '1)'에서 뛰어놓은 2칸 사이에 배치하면된다.

 

즉, 처음 이동인 '1)'을 통해 위에서 본 예시인 '간격 중 하나가 2인 경우'와 같은 상태가 된다.

 

그림으로 보면 다음과 같다.

 

 

 

 

 

테스트 케이스가 '1, 5, 10'일때

간격은 다음과 같다

• 1번, 5번 간격 = 5 - 1 = 4
• 10번, 5번 간격 = 10 - 5 = 5 

 

이동할 수 있는 경우의 수는 2개다.

1) 왼쪽 끝점인 주황색 소를 먼저 이동해보는 경우

2) 오른쪽 끝점인 파란색 소를 먼저 이동해보는 경우

 

우선, 주황색 소를 먼저 이동시키는 경우를 보자.

 

 

 

 

 

 

왼쪽 주황색(1번) 소 부터 이동해보는 경우

이동 횟수	주황색 소	초록색 소	파란색 소	배치 순서
0	1	5	10	1 - 5 - 10
1	7	5	10	5 - 7 - 10
2	7	5	6	5 - 6 - 7

 

👉총 2회

 

 

 

 

 

 

다음으로 파란색 소 부터 이동시키는 경우를 보자

오른쪽 파란색(10번) 소 부터 이동해보는 경우

이동 횟수	주황색 소	초록색 소	파란색 소	배치 순서
0	1	5	10	1 - 5 - 10
1	1	5	3	1 - 3 - 5
2	4	5	3	1 - 3 - 4

 

👉총 2회

 

 

 

 

 

 

최대 이동 횟수

 

최대 이동횟수를 만들기 위해서는 소를 1칸씩 이동시키면된다.

간격이 제일 큰 경우를 선택하여 간격만큼 이동시키면

최대 이동횟수를 구할 수 있다.

 

중요한건 최대 이동횟수 = (큰 간격 - 1)이다.

(간격만큼 다 이동시키면 두 소가 겹치게 된다.)

 

테스트 케이스가 '1, 5, 10'일때

간격은 다음과 같다

• 1번, 5번 간격 = 5 - 1 = 4
• 10번, 5번 간격 = 10 - 5 = 5

 

 

그림으로 봐보자.

 

 

 

 

 

 

 

큰 간격인 5를 채우기 위해 주황색 소를 먼저 이동시킨다.

이동 횟수	주황색 소	초록색 소	파란색 소	배치 순서
0	1	5	10	1 - 5 - 10
1	9	5	10	5 - 9 -10
2	9	5	8	5 - 8 - 9
3	7	5	8	5 - 7 - 8
4	7	5	6	5 - 6 - 7

 

👉 총 4회

 

그림에서는 주황소, 파란소를 움직였지만

주황소, 초록소를 이동시켜도 동일한 결과를 얻을 수 있다.

 

 

 

 

---

💭 처음에 문제를 제대로 이해 못 하고

반복문을 사용하며 풀었다.

이후, 이해한 뒤에는 아하! 했던 문제

천천히 문제를 읽어보며 풀어보자