[백준/BOJ20002] 사과나무

[백준/BOJ]

문제 # 20002

 

내가 작성한 코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int[][] map;
		
		int n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		
		for(int y=1; y<=n; ++y) {
			String[] input = br.readLine().split(" ");
			for(int x=1; x<=n; ++x) {
				map[y][x] = Integer.parseInt(input[x-1]);
			}
		}
		int[][] sums = fillSums(map, n);
		
		int ans = -(int)1e6;
		for(int y=1; y<=n; ++y) {
			for(int x=1; x<=n; ++x) {
				int val = findProfit(y, x, n, sums, map);
				ans = Math.max(ans, val);
			}
		}
		
		StringBuilder sb = new StringBuilder();
        sb.append(ans);
        bw.write(sb.toString());
        bw.close();
        br.close();
	}

	private static int findProfit(int y, int x, int n, int[][] sums, int[][] map) {
		int ret = map[y][x];
		
		for(int size=1; size<=n-Math.max(y, x); ++size) {
			int ny = y + size;
			int nx = x + size;
			if(ny > n || nx > n) break;
			
			int  sum = sums[ny][nx] - sums[y-1][nx] - sums[ny][x-1] + sums[y-1][x-1];
			
			ret = Math.max(ret, sum);
		}
		return ret;
	}

	private static int[][] fillSums(int[][] map, int n) {
		int[][] nMap = new int[n+1][n+1];
		
		for(int y=1; y<n+1; ++y) {
			for(int x=1; x<n+1; ++x) {
				nMap[y][x] = map[y][x] + nMap[y-1][x] + nMap[y][x-1] - nMap[y-1][x-1];
			}
		}
		
		return nMap;
	}

}

 

풀이 및 배운 점

처음에는 누적합이라고 생각하지 못하고 풀어서 오답이 나왔다.

두 번째는 누적합이라고 생각했으나, (0, 0)부터 입력값을 넣어 분기를 둬야하는 부분에서 로직이 잘못돼 오답이 나왔다.

마지막으로 (1, 1)부터 입력값을 넣어 올바른 답을 구할 수 있었다.

 

이전에는 2차원 배열로 누적합을 구할경우, (1, 1)부터 넣는 것이 익숙했었는데, 자주 풀지 않다보니 잊어버렸다. 빠르게 유형을 알아채고 풀어야 했는데,,, 힝구다.