BOJ 12796 : 나의 행렬곱셈 답사기

• 문제 링크 : boj.kr/12796
• 난이도 : G5
• 태그 : 애드혹, 해 구성하기

12796번: 나의 행렬곱셈 답사기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int k;
    cin >> k;
    cout << "3\n1 1 1 " << k+1;

    return 0;
}

---

풀이

행렬이 4개 이상인 경우에는 생각하기 어려우므로 3개일때 가능한지 생각해보자.

행렬이 3개이고 각 행렬의 크기가 (a,b), (b,c), (c,d)라고 하자. 이때 가능한 연산횟수는 a*b*c+a*c*d, b*c*d+a*b*d이다. 

b*c*d+a*b*d가 항상 더 크다고 가정하고 차를 구해보자. 이때 두 수의 차는 cd(b-a)+ab(d-c)이다.

a=b=1이라고 하면 두 수의 차는 d-c가 되고 이를 k로 만드는건 쉽다.