Codeforces Round #420. Div 2. A. - Okabe and Future Gadget Laboratory

원문 :

Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by nsquare grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and ax, y ≠ 1, there should exist two indices s and t so that ax, y = ax, s + at, y, where ai, j denotes the integer in i-th row and j-th column.

Help Okabe determine whether a given lab is good!

Input

The first line of input contains the integer n (1 ≤ n ≤ 50) — the size of the lab.

The next n lines contain n space-separated integers denoting a row of the grid. The j-th integer in the i-th row is ai, j (1 ≤ ai, j ≤ 105).

Output

Print "Yes" if the given lab is good and "No" otherwise.

You can output each letter in upper or lower case.

-----------------------------------------------------------------------------------------------------------

n * n 정사각형 형태로 숫자 input이 들어온다.

각 숫자들은 1~10^5 까지의 값을 가질 수 있다.

1을 제외한 각 숫자들은 다른 숫자 2개의 합으로 나타날 수 있는데,

선택한 숫자와 같은 행에서 1개, 같은 열에서 1개를 골라야 한다.

-----------------------------------------------------------------------------------------------------------

제출한 소스코드 : 

#include<iostream>
#include<stdio.h>

using namespace std;
int main()
{
	int num;
	cin >> num;
	int **p = new int*[num];

	for (int i = 0; i < num; i++) {
		p[i] = new int[num];
	}

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			cin >> p[i][j];
		}
	}

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			bool flag = true;
			if (p[i][j] == 1) continue;
			for (int k = 0; k < num; k++) {
				for (int l = 0; l < num; l++) {
					if (p[i][j] == p[i][k] + p[l][j]) flag = false;
				}
			}
			if (flag) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;


	for (int i = 0; i < num; i++) {
		delete[] p[i];
	}
	delete p;

	return 0;
}

4중 반복문으로 생각없이 기능만 되게 구현했는데 Accepted 되었다.

Input의 크기가 작아서 그런가...

50 * 50이 최대니까

일단 모든 수를 돌려면 2500번을 기본으로 돌아야 할 것이고

추가적으로 1이 아닌 수들에 대해 각 행과 열에 수들을 검사해야한다.