백준 25683, 행렬 곱셈 순서 4

개요

문제 링크
실버 1, Greedy
크기가 단조감소하는 행렬 곱셈의 연산 순서의 최소화

---

접근

1. 크기가 단조감소하면 당연히 큰 쪽부터 혹은 작은 쪽부터 곱해 나가야 할 것 같은데, 왜 그런지가 명확하지 않음.
2. 아래 상황을 가정해보자

   .....{r[i-1],c[i-1]}, {r[i], c[i]}, {r[i+1], c[i+1]}.....
   r[i-1] >= r[i] >= r[i+1]
   c[i-1] >= c[i] >= c[i+1]
   c[i-1] = r[i], c[i] = r[i+1]

   1) 왼쪽부터 하는 경우

   sum_left = r[i-1]*r[i]*c[i] + r[i-1]*r[i+1]*c[i+1]
   = r[i-1]*c[i-1]*c[i] + r[i-1]*r[i+1]*c[i+1]

   2) 오른쪽부터 하는 경우

   sum_right = r[i]*c[i]*c[i+1] + r[i-1]*c[i-1]*c[i+1]
   = r[i]*r[i+1]*c[i+1] + r[i-1]*c[i-1]*c[i+1]

   둘을 비교해보자.

   sum_left - sum_right = r[i-1]*c[i-1]*(c[i]-c[i+1]) + r[i+1]*c[i+1]*(r[i-1]-r[i])
   c[i]-c[i+1] >=0 && r[i-1]-r[i] >=0 이므로
   sum_left >= sum_right

   오른쪽부터 해주는 것이 이득이 된다.

---

Pseudo code

for (i = 오른쪽부터)
    sum += r[i]*c[i]*c[n]

---

Source code

#include <bits/stdc++.h>
using namespace std;

using ld = long long;
int main() {
    int n;
    cin >> n;
    ld r[n], c[n];
    for (int i=1; i<=n; i++)
        cin >> r[i] >> c[i];

    ld sum = 0;
    for (int i=n-1; i>=1; i--)
        sum += r[i]*c[i]*c[n];
    cout << sum;
}