2828. [Python]사과 담기 게임

1. 문제

 

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

2828번: 사과 담기 게임

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 구현, 그리디 알고리즘

 

3. 파이썬 코드

 

# 게임기 크기, 바구니 크기
N, M = map(int, input().split())
# 몇 개의 사과가 들어오는 지
T = int(input())
# 사과들의 위치 리스트
apples = []
# 사과 추가
for _ in range(T):
    apples.append(int(input()))
# 가장 먼 길이의 사과 위치
max_value = max(apples)
# 게임기 길이보다 제일 먼 사과의 위치가 작은 경우 N 값을 먼 길이 사과로 갱신
if max_value < N:
    N = max_value
# 몇번 움직였는지 갯수파악
cnt = 0
# index 값 증가
index = 0
# 현재 바구니 왼쪽끝의 위치
pos = 0
# T번 시행
while index < T:
    # base_value 값을 사과 리스트의 한개씩 순차적으로 넣어줌
    base_value = apples[index]
    # 만약 바구니 안에 값이 있을 경우 무시
    if base_value > pos and base_value <= pos+M:
        pass
    # 그 외의 경우
    else:
        # 만약 바구니 오른쪽 끝이 사과의 위치보다 작은 경우
        if (pos+M) < base_value:
            # 갯수 파악해주는 변수에 사과의 위치 - 끝의 위치
            cnt += (base_value-(pos+M))
            # 이후 왼쪽 끝을 사과의 위치에서 M 만큼 빼줌(바구니 길이)
            pos = base_value-M
        # 왼쪽 끝의 값이 현재 사과의 위치보다 크거나 같은 경우
        elif pos >= base_value:
            # 갯수 파악하는 변수에 현재 바구니 왼쪽끝의 위치에서 현재 사과위치 -1을 더해줌
            # 앞선 조건에서 pos > 으로 설정했기 때문에 -1을 해줌
            cnt += (pos-(base_value-1))
            # 이 또한 위 주식과 마찬가지
            pos = base_value-1
            # 0보다 작아졌을 경우 0으로 초기화
            if pos < 0:
                pos = 0
    index += 1
print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 이 문제가 왜 그리디 알고리즘 인지 문제를 풀고난 후에야 생각을 했다.
• 처음 문제를 이해하기론 바구니가 왼쪽에서 움직이면 우측 끝까지 가야하는 것으로 생각을 하고 계속해서 코드를 구현하여 오답을 많이 냈다.
• 문제를 보고 계속 보며 생각을 하다가 바구니가 끝이 아니라 최대 사과의 위치 까지만 움직이는 것이 맞고 한 사과를 담았을 경우 그 다음 사과까지 거리를 뺴준 만큼 cnt 값을 증가시킨 후 현재 바구니의 위치를 갱신해 주는 것으로 문제를 해결 했다.
• 여기서 주의할 점은 바구니가 왼쪽 > 오른쪽 이동 할 경우와 오른쪽 > 왼쪽 이동하는 경우 위치(pos)를 주의해 줘야 했다.
• 나는 pos 가 왼쪽 pos + M 이 오른쪽으로 진행하고 pos 초과 pos+M 이하로 조건을 설정했다. 이에 맞게 왼 > 오 이동의 경우 사과의 위치가 범위 내일 경우 cnt 값은 유지한 후 조건 밖인 경우 cnt 값과 pos 값을 새로 갱신해주는 식으로 계산했다.
• 오 > 왼 의 경우는 pos 값을 기준으로 위치를 잡았고 pos 초과 pos + M 이하라서 사과 위치를 pos 에 갱신 할 때 -1 을 더 해줬다.
• 다 풀고난 후 각각 사과의 위치까지 최선의 선택을 진행하기 때문에 그리디 알고리즘이 맞다는 생각을 하게 되었고 문제 자체가 쌩 구현 문제이다 보니 시간이 많이 소요됐던 것 같다.

5. 문제를 푸는데 도움이 되는 지식

 

• 구현
• 그리디 알고리즘