[C++] 백준 12796 - 나의 행렬곱셈 답사기

0. [c++] 백준  -

https://www.acmicpc.net/problem/12796

1. 풀이

이게 수학적으로 접근을 하면 정말정말정~말 쉽게 풀 수 있는 문제였다.

하지만, 나의 머리로는 이러한 아이디어가 나오지 않았기에.... 다른 블로그를 참조하였다.

우선, 출처는 https://blog.encrypted.gg/138를 보고 참고하였다.

정말 단순하게 접근하여 3개의 행렬을 가지는 배열을 만들어보겠다.

(1*1), (1*1), (1*k)라는 3개의 행렬이 만들어졌다.

이 3개의 행렬의 곱셈의 횟수가 어떻게 되는지 분석해보자.

1) 1*1*1 + 1*1*k = 1+k

2) 1*1*k + 1*1*k = 2k

딱 두가지의 경우가 생기게 된다. 이때, 구하는 값은 큰 값에서 작은 값을 빼는 것이므로, 

K>2인 경우, 2k - (1+k) = k -1이 되게 된다.

이때, 조금만 값을 수정하여 k 대신 k+1이란 값을 대입하면, 2(k+1) - (1+k+1) = k라는 아름다운 값을 구해낼 수 있었다.

이러한 점을 활용하여 코드를 만들면 완성이다.

2. 소스코드

#include<iostream>
 
using namespace std;
 
void matrix(int K) {
    cout << 3 << endl;
    cout << "1 1 1 " << K + 1;
}
 
int main() {
    int K;
    cin >> K;
 
    matrix(K);
 
    return 0;
}

3. 참고

https://blog.encrypted.gg/138

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!