[백준 22940번] 선형 연립 방정식 (C++)

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

22940번: 선형 연립 방정식

 

다른 풀이가 당연히 있겠지만, 컴퓨터공학을 전공한다면 Gauss - Jordan 소거법을 사용할 듯 하다.

선형대수학에서 배운 기본 행 연산을 통해 계수행렬을 RREF(Reduced Row Echelon Form)으로 만들는 과정을 그대로 구현하면 된다.

---

 

이 문제에서는 주어지는 행렬이 최대 6 by 6이고, 계수들도 모두 10까지의 자연수로만 이루어져 있는데 과정 중에 소숫점을 얼마나 신경써야할까 했지만, 그냥 통과됐다.

기본 행 연산을 하다가 다음 행에 leading1이 없는 경우 행 교환하는 것만 잊지 않으면 단순 구현이다.

 

#include <cstdio>
#include <algorithm>

using namespace std;

int n;
double arr[10][10];

int main(){
	scanf("%d", &n);
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			scanf("%lf", &arr[i][j]);
		}
	}
	for(int i = 0; i < n; i++){
		double pivot = arr[i][i];
		if(!pivot){
			for(int j = i+1; j < n; j++){
				if(arr[j][i] != 0){
					for(int k = 0; k <= n; k++){
						swap(arr[i][k], arr[j][k]);
					}
					pivot = arr[i][i];
					break;
				}
			}
		}
		for(int j = i; j <= n; j++){
			arr[i][j] /= pivot;
		}
		for(int j = i+1; j <= n; j++){
			double tmp = arr[j][i];
			for(int k = i; k <= n; k++){
				arr[j][k] -= (arr[i][k] * tmp);
			}
		}
	}
	
	for(int i = n-1; i >= 0; i--){
		for(int j = i-1; j >= 0; j--){
			double tmp = arr[j][i];
			for(int k = i; k <= n; k++){
				arr[j][k] -= (arr[i][k] * tmp);
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		printf("%.0lf ", arr[i][n]);
	}
	
}

 

 

이보다 더 어려운 문제로는 20307번이 있다.

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

20307번: RREF

똑같이 Gauss소거법을 구현하면 되지만 분수로 정확하게 출력해야하기 때문에 더 복잡하다.

C계열의 언어로만 제출할 수 있게 한 것을 보면 파이썬의 Fraction모듈을 막기 위한 것 같다.