취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11579번 문제인 초차원전쟁 이나이다.
문제는 아래 링크를 확인하자.

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

주어진 행사다리꼴(Row Echelon Form; REF)의 벡터의 음이 아닌 정수 상수배의 합으로 원하는 벡터를 만들 수 있는지 확인하는 문제이다.

첫 번째 행부터 차례대로 주어진 행을 보면서 처리하면, 각 행의 첫 번째 1이 위치한 열은 앞으로의 과정에서 지금의 행으로만 값을 변경할 수 있음을 관찰하자. 따라서 각 행마다 첫 1이 위치한 열의 값을 일치시키려면 각 벡터에 어떤 상수를 곱해야 하는지를 하나하나 구해 문제를 해결할 수 있다.

여신은 최대 20억번 움직일 수 있다는 제약이 있으므로, 위의 변경을 위해 필요한 값이 20억이 넘는 경우에는 0을 출력해야 함에 유의하자. 이러한 입력은 실제로 주어질 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll A[500][500], X[500];

void solve() {
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) cin >> A[r][c];
	}
	for (int c = 0; c < N; c++) cin >> X[c];

	ll ans = 0;
	for (int r = 0; r < N; r++) {
		ll C = X[r];
		if (C < 0) {
			cout << 0 << '\n';
			return;
		}
		for (int c = r; c < N; c++) X[c] -= C * A[r][c];
		ans += C;
		if (ans > 2000000000) {
			cout << 0 << '\n';
			return;
		}
	}
	cout << 1 << ' ' << ans << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}