백준 10836번: 여왕벌

문제 설명

• https://www.acmicpc.net/problem/10836
• 맨 왼쪽, 그리고 위쪽에 있는 애벌레는 입력으로 주어지는 숫자만큼 성장합니다.
• 나머지 애벌레는 자신의 왼쪽,왼쪽 위,위와 동일한 크기로 성장합니다.

접근법

• N이 최대 1_000_000으로 2차원 배열의 값을 자주 갱신하면 시간초과가 발생합니다.
• 나머지 애벌레는 입력으로 주어지는 값으로 성장하는 애벌레의 크기가 정해지면 자동으로 정해집니다. (계속 값을 갱신할 필요 없이 최종에 한번만 구하면 됩니다)
• 입력으로 주어지는 값을 매번 2차원 배열에 넣는게 아니라, 1차원 배열에서 그 값을 누적시킨 뒤 한번만 2차원 배열에 넣으면 됩니다.
• 0은 어차피 더해지지 않기 때문에 for문을 돌 필요가 없습니다.

정답

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N  = Integer.parseInt(st.nextToken());
		int M  = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][N];

		int[] total = new int[2*N-1];
		Arrays.fill(total, 1);
		
		for (int i = 0; i < M; i++) {
			int[] condition = new int[4];
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < 4; j++) {
				condition[j] = Integer.parseInt(st.nextToken())+condition[j-1];
			}
			for (int j = condition[1]; j < condition[2]; j++) {
				total[j] += 1;
			}
			for (int j = condition[2]; j < condition[3]; j++) {
				total[j] += 2;
			}
		}
		selfGrowth(total,board, N);
		restGrowth(board,N);
		
		StringBuilder answer = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				answer.append(board[i][j]+" ");
			}
			answer.append("\n");
		}
		System.out.println(answer.toString());
	}
	
	public static void selfGrowth(int[] condition, int[][] board, int N) {
		
		int idx = 0;
		for (int i = 0; i < N; i++) {
			board[N-1-i][0] += (condition[idx++]);
		}
		for (int i = 1; i < N; i++) {
			board[0][i] += (condition[idx++]);
		}
		
	}

	public static void restGrowth(int[][] board, int N) {
		for (int i = 1; i < N; i++) {
			for (int j = 1; j < N; j++) {
				board[i][j] = Math.max(Math.max(board[i-1][j], board[i][j-1]), board[i-1][j-1]);
			}
		}
	}

}