백준 20972(Spaced Out)

www.acmicpc.net/problem/20972

20972번: Spaced Out

 

N*N의 격자점에 점수가 빠짐없이 있고, 그 N*N의 격자점에서 아무 2*2를 잡아도 소들이 2마리가 되게끔 할때의 격자점 점수의 합의 최대를 구하는 문제

 

우선 그냥 관찰만 한다. 

 

그러다가 관찰을 하다보면 

 

C     C

C     C

C     C

C     C

C     C

C     C

 

이런식으로 음 어떻게 설명을 해야하지 홀수 열들은 모두 같은 배치, 짝수 열들도 모두 같은 배치로 소를 배치할 수 있고, 이번에는 행에서 계산할 수 있다. 

 

그냥 이게 끝 사실 행에서 어떤식으로 바뀌는지 더 자세하게 생각해보려고 하진 않았기 때문에 확실치는 않다.

 

이제부터 그리디 

 

#include<iostream>
#include<algorithm>
using namespace std;

int num[1005][1005];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> num[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		int a = 0, b = 0, c = 0, d = 0;
		for (int j = 0; j < n; j += 2) {
			a += num[i][j];
			c += num[j][i];
		}
		for (int j = 1; j < n; j += 2) {
			b += num[i][j];
			d += num[j][i];
		}
		sum1 += max(a, b);
		sum2 += max(c, d);
	}
	cout << max(sum1, sum2);
}