[백준] 32712번: 다이얼 룰렛

문제

백준 - 32712번: 다이얼 룰렛

분석

다이얼 룰렛을 K번 회전(시계방향 혹은 반시계방향)할 수 있을 때, 최대로 얻을 수 있는 점수를 구하는 문제이다.

최대 N은 200,000, K는 109 이기 때문에 dfs를 통해 모든 경우를 구하면 시간초과가 난다.

그래서 그리디적인 사고가 필요하다.
특정 위치까지 간 다음 남은 회전수를 모두 그 자리에서 왔다갔다하면, 그 경우가 가장 점수를 크게 얻을 수 있다.
따라서 모든 위치를 보기 위해 n과 k중 작은 것만큼 경우를 따져본다.
clock_score에는 특정 위치까지 갈 때 누적되는 점수이다.
누적 되는 값에 남은 회전수(k-i)X기준점이 지나는 점수를 더하여 그 값을 최대값과 계속 비교한다.
입력받은 arr를 뒤집어 반시계 방향으로 움직이는 경우에도 똑같이 계산해준다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = list(map(int, input().split()))
ans = 0
clock_score = 0
for i in range(min(n, k)):
    ans = max(ans, clock_score+(k-i)*arr[i])
    clock_score += arr[i]
arr = arr[::-1]
counter_clock_score = 0
for i in range(min(n, k)):
    ans = max(ans, counter_clock_score+(k-i)*arr[i])
    counter_clock_score += arr[i]
print(ans)

끝으로..

그리디적 사고를 연습할 수 있게 관련 문제를 여럿 풀어봐야겠다.