[백준] 12847 꿀 아르바이트(Python)

해당 게시글에서는 [백준] 12847 꿀 아르바이트 문제를 해설하고 Python을 이용하여 풀고자 한다.

💡 문제 풀이

1522번 문제는 투 포인터에 대한 문제 중에서도 슬라이딩 윈도우 알고리즘 문제에 해당한다.
슬라이딩 윈도우 알고리즘이 된 이유는 다음의 조건 때문이다.

• 한 번이라도 퇴직한 자를 다시 취직 시키지 않는다.(만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)

죽, 준수가 일을 할 수 있는 날(m)이 주어졌을 때 일을 시작한 날(st)로부터 m일 동안 빠짐없이 일해야 한다는 것이다. 따라서 준수가 최대 이익을 얻기 위해선 시작한 날(st)로부터 m일 동안 일했을 때의 이익을 모든 경우에 대해서 구하고 최댓값을 출력해주면 된다. m일이라는 길이가 계속 고정되기 때문에 슬라이딩 윈도우 문제가 되는 것이다.

🔒 코드(시간 초과)

위에서 설명한 풀이에 의해 다음과 같이 코드를 작성했다. 하지만 아래의 코드로 제출하면 시간 초과가 발생한다.

n, m = map(int, input().split())
money = list(map(int, input().split()))

max_val = 0
for st in range(n-(m-1)):
    max_val = max(max_val, sum(money[st:st+m]))
print(max_val)

알고리즘 분류를 확인해보면 슬라이딩 윈도우 뿐만 아니라 누적 합에 해당하는 것을 알 수 있는데, 누적 합을 이용하여 불필요한 연산을 줄일 수 있다.

각 일수에 해당하는 합을 구하는 과정에서 참조하려는 인덱스가 (st)~(st+(m-1))일 때와 (st+1)~(st+m)일 때 (st+1)~(st+(m-1))에 해당하는 값은 공통된 값이다. 따라서 해당 범위에 있는 값들에 대해서는 새롭게 더해주지 않고 이전 값을 이용하면 덧셈에 대한 연산량을 줄일 수 있다.

📂 코드

위의 설명과 같이 누적 합의 개념을 추가적으로 적용하여 아래와 같이 문제를 해결했다.

n, m = map(int, input().split())
money = list(map(int, input().split()))

sum = ans = sum(money[0:m])
for st in range(n-m):
    sum -= money[st]
    sum += money[st+m]
    ans = max(ans, sum)
print(ans)