[백준 28439] 행렬 연산 (연산 찾기) [Python]

백준 28439 - 문제

백준 28439 - 입/출력

---

풀이

모든 행과 열에 대해 연산을 적용해 입력받은 행렬과 비교하는 방법은 시간초과가 날것이 자명하다.

마치 노노그램 게임처럼 그림을 그리듯 테두리의 행/열 값을 가지고 연산을 하면 풀 수 있는 문제다.

 

행/열에 더하는 수를 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번의 연산이 가능하다.

최소는 3번의 연산으로도 충분하다.

즉, 가장 단순하게 테두리의 행/열에서 빈도수가 높은 수를 A(1,1) = R(1) 에서 사용해 다른 행과 열에서 최대한 연산을 적게 하는 방법으로 연산 횟수를 줄일 수 있다.

이는 A(1, j)와 C(1) - A(i, 1) 중 빈도수가 높은 수를 R(1)로 하여 위에서 얻은 수식에 대입하면 연산 횟수를 최소화 할 수 있다. 

위에서 얻은 R, C로 입력받은 행렬과 일치하는 경우에만 필요한 연산을 출력해주자.

---

소스코드

소스코드 보기

---

출처

28439번: 행렬 연산 (연산 찾기)