[SWEA 2805] 농작물 수확하기

문제

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

SW Expert Academy

 

2차원 배열에서 마름모꼴 영역의 합을 구하는 문제 

 

출처 : SWEA

 

나...솔직히 이 문제보고 BFS로 해보려고 했는데...접근 방법이 틀렸으니 맞을리가 있나...

예전에 다룬 포스팅 중 BFS 순회가 빠르다는 뭐 그런 얘기를 하면서 있던 그림을 보고 어떻게 해보려고 했지만 실패!

지금 생각해보니 풀려면 풀 수 있을지도 모른다..ㅎ (거짓말)

 

 

 

 

코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class SWEA_2805 {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		
		for (int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(in.readLine());
			
			int[][] farm = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				String line = in.readLine();
				for (int j = 0; j < N; j++) {
					farm[i][j] = line.charAt(j) - '0';
				}
			}
			
			int s = N / 2;
			int e = N / 2;
		
			int sum = 0;
			
			for (int i = 0; i < N ; i++) {
				for (int j = s; j <= e; j++) {
					sum += farm[i][j];
				}
				
				if(i < N / 2) {
					s--;
					e++;
				} else {
					s++;
					e--;
				}
			}
			System.out.println("#" + test_case + " " + sum);
		} 
	}

}

 

 

 

 

어떻게 풀었는가

- 뭐? 마름모..? 별 찍기 문제에서 봤는데

https://www.acmicpc.net/problem/2444

2444번: 별 찍기 - 7

 

 

출처 : 백준

 

위의 그림을 구현해본 적이 있다면 같은 코드로 구현하면 된다...^^ 

그럼 저것을 어떻게 구현하냐

 

(1) 일단, 2차원 배열의 열(세로줄)을 순회하긴 해야 한다. 다 돌아봐야 하니깐 (0 ~ N) 까지 반복문을 돌린다. 

(2) 그럼 행은 어떻게 이동시켜주면 좋을까(가로줄). 일단 배열의 많은 문제는 인덱스 갖고 놀기이다.

- 0 번째 줄 : 가운데에 있는 인덱스(N/2)

- 1번째 줄 : 가운데에 있는 인덱스 - 1 ~ 가운데에 있는 인덱스 + 1 사이의 값

- 2번째 줄 : 가운데에 있는 인덱스 - 2 ~ 가운데에 있는 인덱스 + 2 사이의 값

...

- N/2번째 줄 : 가운데에 있는 인덱스 - N/2 ~ 가운데에 있는 인덱스 + N/2 사이의 값

 

✅ 여기서 N/2+1 번째 줄부터는 다시 줄어든다

- N/2 + 1번째 줄 : 가운데에 있는 인덱스 - N/2 - 1 ~ 가운데에 있는 인덱스 + N/2 - 1 사이의 값

- N/2 + 2번째 줄 : 가운데에 있는 인덱스 - N/2 - 2 ~ 가운데에 있는 인덱스 + N/2 - 2 사이의 값

...

- N 번째 줄 : 가운데에 있는 인덱스 - N/2 - N/2 ~ 가운데에 있는 인덱스 + N/2 - N/2 사이의 값 (가운데에 있는 인덱스만 남음)

 

 

변수 두개를 가운데에 있는 인덱스로 초기화해준다(s, e 를 N/2 로)

반복문을 돌면서 s와 e를 포함한 가로줄의 수를 더해준다.

그리고 i(세로줄)의 범위에 맞게 s, e를 옮겨주면 된다.  

 

끝!