28439번 - 행렬 연산 (연산 찾기) 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 825 | 260 | 214 | 33.281% |
문제
$N$ 행 $M$ 열로 이루어진 $2$차원 행렬이 있습니다. 이 행렬의 모든 원소는 처음에 $0$입니다.
이 행렬에 다음과 같은 연산을 할 수 있습니다.
- $1$ $r$ $v$
- $1$ 이상 $N$ 이하의 수 $r$과 정수 $v$를 정합니다. $r$번째 행의 모든 원소에 $v$를 더합니다.
- $2$ $c$ $v$
- $1$ 이상 $M$ 이하의 수 $c$와 정수 $v$를 정합니다. $c$번째 열의 모든 원소에 $v$를 더합니다.
이 행렬의 연산을 최소한의 횟수로 진행하여, 주어진 행렬 $A$를 만들고 싶습니다. 만드는 방법을 하나 찾아서 출력하세요.
입력
첫 줄에 행렬 $A$의 크기를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어집니다. $(1 \le N, M;$ $N \times M \le 500\,000)$
다음 $N$개의 줄의 $i$번째 줄에는 $A$의 $i$번째 행의 원소를 의미하는 정수 $M$개가 공백으로 구분되어 주어집니다. 각 수의 절댓값은 $1\,000\,000$ 이하입니다.
출력
연산을 유한 번 사용하여 행렬을 $A$로 만들 수 있는 경우, 첫 줄에 행렬을 $A$로 만드는데 필요한 연산 횟수의 최솟값 $Q$를 출력하세요.
다음 $Q$개의 줄의 각 줄에 필요한 연산을 의미하는 세 정수를 공백으로 구분하여 출력하세요. 각 연산은 다음 중 하나여야 합니다.
- $1$ $r$ $v$ $(1 \le r \le N; -10^9 \le v \le 10^9)$
- $2$ $c$ $v$ $(1 \le c \le M; -10^9 \le v \le 10^9)$
불가능한 경우 첫 줄에 $-1$을 출력하세요.
예제 입력 1
2 3 0 1 -3 2 3 -1
예제 출력 1
3 2 2 1 1 2 2 2 3 -3
예제 입력 2
2 2 1 2 2 4
예제 출력 2
-1
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호