[SWEA][C++] 2805. 농작물 수확하기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GLXqKAWYDFAXB

SW Expert Academy

 

풀이

중앙에 있는 행(마름모의 대각선)은 모든 열의 수익을 더한다.

그리고 위로 갈수록 또는 아래로 갈수록 수익을 더하는 열이 줄어든다.

이러한 점을 이용하여, 중앙 행(n/2 행)과의 차이에 따라 각 행의 수익을 계산할 수 있다.

현재 행과 중앙 행의 차이 = 0일 때, 0 ~ n - 1 열의 수익을 얻을 수 있다.
현재 행과 중앙 행의 차이 = 1일 때, 1 ~ n - 2
현재 행과 중앙 행의 차이 = 2일 때, 2 ~ n - 3
...
각 행에서 num ~ (n - num) 열의 수익을 얻을 수 있다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

int calculate(int n, vector<vector<int>> &v) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int num = abs(n / 2 - i);   // 현재 행과 중앙 행의 차이
        for (int j = num; j < n - num; j++) {
            ans += v[i][j];
        }
    }

    return ans;
}

int main() {
    int T;
    cin >> T;

    for (int test_case = 1; test_case <= T; ++test_case) {
        int n, ans;  // 농장의 크기, 수익

        // 입력
        cin >> n;
        vector<vector<int>> v(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < n; j++) {
                v[i][j] = s[j] - '0';
            }
        }

        // 출력
        cout << '#' << test_case << ' ' << calculate(n, v) << '\n';
    }

    return 0;
}