파이썬 Python | 알고리즘 | 백준 사과 담기 게임

⭕ 파이썬 Python | 알고리즘 | 백준 사과 담기 게임

➡️ 문제링크

• https://www.acmicpc.net/problem/2828

 

➡️ 문제 탐색하기

• 바구니의 초기 위치와 크기가 주어졌을 때, 사과가 떨어지는 위치에 따라 바구니를 최소한으로 이동시키는 문제이다. 불필요한 이동을 최소화하여 최종 이동 거리를 계산하는 것이 목표이다.

---

1. 사과가 바구니 안에 떨어지는 경우: 바구니가 이미 사과의 위치를 포함하고 있다면 바구니를 움직일 필요가 없다. 이동 거리는 0이 된다.
2. 사과가 바구니 왼쪽에 가깝게 떨어지는 경우: 바구니를 왼쪽으로 이동시켜야 한다. 이때, 사과와 바구니의 왼쪽 끝 간의 거리만큼 바구니를 이동시키면 된다. 
3. 사과가 바구니 오른쪽에 가깝게 떨어지는 경우: 바구니를 오른쪽으로 이동시켜야 한다. 이 경우도 사과와 바구니의 오른쪽 끝 간의 거리만큼 이동한다.

 

➡️ 코드 설계하기

• 스크린의 크기 N과 바구니의 크기 M을 입력받아 초기 조건을 설정한다. 바구니의 위치를 left와 right로 설정하여 바구니의 왼쪽 끝과 오른쪽 끝을 나타낸다.
• 사과의 개수 J를 입력받고, 각 사과의 위치를 순차적으로 탐색한다. 모든 사과를 한 번씩 순회하며 바구니의 위치를 조정한다.
• 각 사과에 대해 바구니의 위치를 확인하여, 사과가 바구니 범위 안에 들어오는 경우에는 이동하지 않는다. 사과가 바구니 범위 밖에 있는 경우, 사과가 떨어지는 위치에 따라 바구니를 왼쪽 또는 오른쪽으로 이동시킨다. 
• 바구니를 이동시킨 거리를 계속 합산하여 최종적으로 이동한 총거리를 출력한다. 

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차 

• 시간 88ms
• 시간 복잡도는 O(J)로, 사과의 개수에 비례해 연산이 이루어진다. 

import sys

N, M = map(int, sys.stdin.readline().split())
J = int(sys.stdin.readline())

left = 0
right = M - 1

count = 0  

for _ in range(J):
    loc = int(sys.stdin.readline()) - 1 

    if (loc < left):  
        count += left - loc
        left = loc
        right = left + M - 1
    elif (loc > right): 
        count += loc - right
        right = loc
        left = right - M + 1
   

print(count)

 

 

➡️ 정답 코드

import sys

# 스크린 크기 N과 바구니 크기 M을 입력받음
N, M = map(int, sys.stdin.readline().split())

# 사과의 개수 J를 입력받음
J = int(sys.stdin.readline())

# 바구니의 초기 위치를 설정
left = 0
right = M - 1

# 이동 거리 누적합 변수 초기화
count = 0  

# 각 사과의 위치에 대해 반복
for _ in range(J):
    loc = int(sys.stdin.readline()) - 1  # 사과의 위치 입력받음

    # 사과가 바구니 왼쪽에 떨어진 경우
    if loc < left:  
        count += left - loc  # 이동 거리 계산 및 누적
        left = loc  # 바구니의 새로운 위치 설정
        right = left + M - 1  # 바구니 오른쪽 위치 갱신
    # 사과가 바구니 오른쪽에 떨어진 경우
    elif loc > right: 
        count += loc - right  # 이동 거리 계산 및 누적
        right = loc  # 바구니의 새로운 위치 설정
        left = right - M + 1  # 바구니 왼쪽 위치 갱신

# 최종 이동 거리 출력
print(count)