이차원 배열의 합 최댓값
시간 제한2초메모리 제한128 MB
6x6 숫자 격자에서 행, 열, 대각선 두 개에 1을 더하거나 빼는 연산(10으로 순환)을 반복해 전체 합의 최댓값을 구하는 문제입니다.
문제
6×6 배열에 0 이상 9 이하의 숫자가 들어 있다. 아래 연산을 원하는 만큼 수행해 배열 원소의 총합을 최대화하려고 한다.
- 1 이상 6 이하의 정수 i를 골라, i번째 행의 여섯 수에 모두 1을 더한다.
- 1 이상 6 이하의 정수 i를 골라, i번째 행의 여섯 수에서 모두 1을 뺀다.
- 1 이상 6 이하의 정수 i를 골라, i번째 열의 여섯 수에 모두 1을 더한다.
- 1 이상 6 이하의 정수 i를 골라, i번째 열의 여섯 수에서 모두 1을 뺀다.
- 왼쪽 위에서 오른쪽 아래로 이어지는 대각선의 여섯 수에 모두 1을 더한다.
- 오른쪽 위에서 왼쪽 아래로 이어지는 대각선의 여섯 수에 모두 1을 더한다.
- 왼쪽 위에서 오른쪽 아래로 이어지는 대각선의 여섯 수에서 모두 1을 뺀다.
- 오른쪽 위에서 왼쪽 아래로 이어지는 대각선의 여섯 수에서 모두 1을 뺀다.
각 연산은 횟수 제한 없이 사용할 수 있다. 모든 수는 한 자리 숫자로 유지되므로, 9에 1을 더하면 0이 되고 0에서 1을 빼면 9가 된다.
다음 배열을 보자.
5 9 7 1 5 8
2 5 3 5 2 0
6 8 1 5 0 3
4 8 2 6 9 2
9 1 6 5 3 2
7 0 2 4 3 1
1번째 행에 1을 더하면 배열은 다음과 같이 바뀐다.
6 0 8 2 6 9
2 5 3 5 2 0
6 8 1 5 0 3
4 8 2 6 9 2
9 1 6 5 3 2
7 0 2 4 3 1
이 상태에서 1번째 열의 수에서 1을 빼면 배열은 다음과 같이 바뀐다.
5 0 8 2 6 9
1 5 3 5 2 0
5 8 1 5 0 3
3 8 2 6 9 2
8 1 6 5 3 2
6 0 2 4 3 1
입력
배열을 나타내는 정수가 6개의 줄에 6개씩 주어진다. 각 수는 0 이상 9 이하의 정수이다.
출력
가능한 배열 원소 합의 최댓값을 첫째 줄에 출력한다.