정화 코딩

https://www.acmicpc.net/problem/12850 어떤 인접 행렬이 "1분만에 이동할 수 있는 경로"라고 하면, 인접 행렬의 d 거듭제곱은 "d분만에 이동할 수 있는 경로"이다.이 사실만 알면 문제를 쉽게 풀 수 있다. (선형대수학에서 배운다고들 하는데 나는 왜 기억이 안 나지)단순 d 제곱을 하면 시간초과가 나므로 분할 정복을 이용한 거듭제곱을 사용해주어야 한다. #include #include using namespace std;int MOD = 1000000007;vector> e;vector> mul(vector> a, vector> b) { vector> c(8, vector(8, 0)); for (int i = 0; i > pow(vector> a, int x) {..

https://www.acmicpc.net/problem/2568 딱 전깃줄 문제와 가장 긴 증가하는 부분 수열 5 문제를 합친 문제이다. 전깃줄 문제 풀이: https://jungh150c.tistory.com/110가장 긴 증가하는 부분 수열 5 문제 풀이: https://jungh150c.tistory.com/109 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> a(n + 1); a[0].first = a[1].first = 0; for (int i = 1..