SWEA 2805. 농작물 수확하기(Java)

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

이 문제는 2가지 방법으로 풀 수 있다.

1. 별 찍기하듯이

2. 델타 탐색

 

먼저, 문제에서 농작물을 수확할 수 있는 정사각형 마름모 형태의 별을 찍어보면,

N = 7일 때

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if(i < N/2) {    
            if(j >= N/2 - i && j <= N/2 +i) {
                System.out.print("*");
            }
            else {
                System.out.print(" ");
            }
        }
        else { 
            if(j >= N/2 - (N-1) + i && j <= N/2 + (N-1) - i ) {
                System.out.print("*");
            }
            else {
                System.out.print(" ");
            }
        }
    }
    System.out.println();
}

이를 이용해 문제를 풀어보자. 농작물 수확해서 얻는 이익을 profit이라는 변수라고 하였다.

import java.util.Scanner;
 
public class List_Sequantial {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
 
            int N = sc.nextInt();
            int[][] farm = new int[N][N];
 
            // 한 줄씩 입력 받아서 char로 하나씩 쪼갠다.
            // sc.nextInt()로 String 14054을 입력받고,
            // toCharArra()로 char 1, char 4...char 4의 배열로 바꿔준다.
            // 즉, ['1', '4', '0', '5', '4']가 되는 것이다.
            for (int i = 0; i < N; i++) {
                char[] tempArr = sc.next().toCharArray();
                for (int j = 0; j < N; j++) {
                    farm[i][j] = tempArr[j] - '0';
                }
            }
            int profit = 0; 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i < N / 2) {
                        if (j >= N / 2 - i && j <= N / 2 + i) {
                            profit = profit + farm[i][j];
                        }
                    } else {
                        if (j >= N / 2 - (N - 1) + i && j <= N / 2 + (N - 1) - i) {
                            profit = profit + farm[i][j];
                        }
                    }
                }
            }
            System.out.println("#" + (tc+1) + " " + profit);
        }
    }
}
 

 

이번엔 델타 탐색을 통해 문제를 풀어보도록 한다.

먼저 N=5일때, 수확이 가능한 부분을 색칠해서 나타내면(노란색 부분)

N*N 2차원 배열의 중앙을 기준으로 생각해보자.

중앙을 기준으로 2칸 이동을 한 경우에만 수확이 가능함을 알 수 있다.

즉, 위로 두칸이든 위로 한칸 오른쪽 한칸이든 이동한 횟수 또는 칸수가 2이기만 하면 된다.

이를 이용해서 풀어보자.

import java.util.Scanner;
 
public class Solution {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
 
            int N = sc.nextInt();
            int[][] farm = new int[N][N];
 
            // 한 줄씩 입력 받아서 char로 하나씩 쪼갠다.
            // sc.nextInt()로 String 14054을 입력받고,
            // toCharArra()로 char 1, char 4...char 4의 배열로 바꿔준다.
            // 즉, ['1', '4', '0', '5', '4']가 되는 것이다.
            for (int i = 0; i < N; i++) {
                char[] tempArr = sc.next().toCharArray();
                for (int j = 0; j < N; j++) {
                    farm[i][j] = tempArr[j] - '0';
                }
            }
            int profit = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if ((Math.abs(i - N / 2) + Math.abs(j - N / 2)) <= N / 2) {
                        profit = profit + farm[i][j];
                    }
                }
            }
            System.out.println("#" + (tc+1) + " " + profit);
        }
    }
}