[백준 28439] 행렬 연산 (연산 찾기) [Python]
풀이 모든 행과 열에 대해 연산을 적용해 입력받은 행렬과 비교하는 방법은 시간초과가 날것이 자명하다. 마치 노노그램 게임처럼 그림을 그리듯 테두리의 행/열 값을 가지고 연산을 하면 풀 수 있는 문제다. 행/열에 더하는 수를 R(i), C(j)라 한다면, 다음을 만족한다. R(i) + C(j) = A(i, j) C(j) = A(i, j) - R(i) = A(1, j) - R(1) R(i) = A(i, j) - C(j) = A(i, 1) - C(1) = A(i, 1) - { A(1, 1) - R(1) } = A(i, 1) - A(1, 1) + R(1) 위와 같은 수식을 통해 행렬을 만들 수 있다. 하지만, 이러한 연산의 횟수를 최소화 해야한다. 아래의 예제를 살펴보자. 위 행렬을 만들기 위해 최대 5번의 연..
2023. 8. 19.
