알고리즘 greedy, dp 시간복잡도 $O(N)$ 풀이 $ad, b->c)$보다 항상 비용이 작음이 증명된다. 따라서 절대 소가 밀릴 일이 없는 지점에서 시계 방향으로 돌 때 가장 가까운 0으로부터 순차적으로 밀어주면 된다. dp를 통해 가장 많이 밀린 지점을 구할 수 있으며, $O(N)$으로 끝에 있는 0부터 채워주면 된다. 코드 #include using namespace std; #define ll long long int N, a[100005], dp[100005]; ll ans; ll add(ll b, ll n) { ll r = 0; for (ll i = 0; i >N; for (int i =..
