[SWEA 2805번] 농작물 수확하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AV7GLXqKAWYDFAXB&categoryId=AV7GLXqKAWYDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=4&pageSize=10&pageIndex=1

SW Expert Academy

 

 

import java.io.*;
import java.util.*;

public class Solution {
    static int[][] map;
    static int sum;

    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test < T + 1; test++) {
            N = Integer.parseInt(br.readLine());
            sum = 0;
            map = new int[N][N];

            for (int i = 0; i < N; i++) {
                String num = br.readLine();
                for (int j = 0; j < num.length(); j++) {
                    map[i][j] = Integer.parseInt(String.valueOf(num.charAt(j)));
                }
            }

            int front = N / 2 + 1;
            int back = N / 2;
            farm(front, back);
            System.out.println("#" + test + " " + sum);
        }
    }

    public static void farm(int front, int back) {
        int fX = 0;
        int fY = back;

        int bX = 1;
        int bY = back;

        for (int i = 0; i < front; i++) {
            int fnX = fX;
            int fnY = fY;
            for (int j = 0; j < front; j++) {
                sum += map[fnX][fnY];
                fnX += 1;
                fnY -= 1;
            }
            fX += 1;
            fY += 1;

        }

        for (int i = 0; i < back; i++) {
            int bnX = bX;
            int bnY = bY;
            for (int j = 0; j < back; j++) {
                sum += map[bnX][bnY];
                bnX += 1;
                bnY -= 1;
            }
            bX += 1;
            bY += 1;

        }
    }

}

 

문제를 읽고 여러 가지 방법을 고민한 끝에, 대각선 방향으로 내려가며 합을 구하는 방식으로 문제를 해결했다. 핵심 아이디어는 맨 꼭대기에서 시작해 대각선 왼쪽 아래 방향으로 내려가고, 이후 오른쪽으로 한 칸 이동한 뒤 다시 같은 방식으로 순회하는 것이다. 이 과정을 모두 마치면 front 순회가 끝나며, 이후 back도 같은 방식으로 처리하면 된다. 전체적으로 간단한 알고리즘 문제였다.