[백준] 20669. Close To You

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

문제요약

• 그래프가 주어지고 이동을 함 (1번, 2번, ... K번)
• 시작점 그룹이 있고, 종료점 그룹이 있음
• 서로다른 모든 경우의 수 구하기
• N = 100, K = 1000000
• 공식 풀이 : https://drive.google.com/file/d/1MA4W5Jic9goqLtH6fjn0ymgNF8GydA_O/view

접근법

• 인접행렬 + 그래프로 이동, 이동 하는 문제임
• "K 번만" 이동했을때를 구하면 행렬거듭제곱으로 해서 구하면 되겠으나
• 이 문제는 sum(1번, 2번, ..., K번)이라서 한 번 더 문제를 비틀었음
• 일단 주어진 조건으로 이동에 대한 행렬을 만들었다고치면 : mat(N by N)
• x 번 이동 행렬은 ${mat ^ x}$ 임
• 구하려고 하는 값은 ${mat ^ 1 + mat ^ 2 + ... + mat ^ k}$
• 거듭제곱 시간 복잡도 : ${log(k) * n^3}$
• 각각의 거듭제곱을 일일이 구해서 더하면 ${log(k) * n^3 * k}$
• 거듭제곱 합을 편의상 ${1 + 2 + 3 + ... + K}$ 로 표현하면
• 분할이 가능함 : ${(1 + 2 + ... + mid) + mid(1 + 2 + ... + mid)}$
• 짝/홀인 경우 적절히 배분

구현

• 행렬을 [][]로 구현하면 여러모로 불편해서 vector<vector> 형식 사용
  • typedef vector<vector> mat
• 더하기, 곱하기는 연산자 오버로딩 사용
  • mat operator +(mat a, mat b)
  • mat operator *(mat a, mat b)
• cpp에서 함수에 객체를 전달하고 리턴할때 동작원리를 정확히는 모르겠으나, vector는 값을 복사해서 전달하고, 대입 연산에서는 값을 복사해서 전달하는 것 같음(reference 사용하려면 & 를 붙이니까)

시간 초과

• 시간초과가 발생했고, 거듭제곱 연산이 많이 사용되는 것 같았음
• 했던 거듭제곱을 또 사용하는 것 같아서 map을 이용해서 cache를 사용했음
• 다른 사람 구현은 어떤지 분석해봐야함
  • 공식해설은 시작, 끝 간선을 하나로 두고
  • 끝 간선에서 self 순환 간선을 추가하였음
  • 경로가 t인 것을 구하면 결과적으로 t - 1, t - 2도 구하는 효과....