[백준 10836] 여왕벌 (JAVA)

문제 링크: https://www.acmicpc.net/problem/10836

10836번: 여왕벌

1. 주의할 점

- 매일마다 애벌레의 크기를 바꾸면 시간초과가 발생한다

- 0,1,2의 순서로 증가하는 크기를 나타내므로, 좌, 좌상, 상과 비교할때 제일 많이 자란 애벌레는 무조건 상이다

 

2. 구현

- 매일 자라는 애벌레의 크기를 Order[] 배열에 담는다. 단, 1씩 자라기 시작하는 곳, 2씩 자라기 시작하는 포인트에서만 ++한다

- 왼쪽과 상단의 가장자리에 서식하는 애벌레부터 Order배열에 적힌 수만큼 Sum에 더하고, Sum을 Arr[][](애벌레의 크기를 기록)배열에 기록한다 -> 글재주가 없어서 이해하기 어렵겠지만 이해하면 많은 도움이 된다

- 이외의 애벌레는 자신의 상단에 해당 하는 애벌레의 크기만큼 할당한다. 단, 모든 애벌레가 자신의 상단에 위치한 애벌레의 크기만큼 증가하므로 0번째 행에 적힌 값을 그대로 가져온다.

- 출력할때, 가장 처음에 애벌레의 크기는 1이므로 1씩 더해서 출력한다 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_bj_10836_여왕벌 {
	
	static int arr[][],n,m,order[];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str= br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		
		//초기화
		arr = new int[m][m];
		order = new int[2*m];
		for(int t=0;t<n;t++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			int idx1 = Integer.parseInt(st.nextToken());
			int idx2 = Integer.parseInt(st.nextToken());
			int idx3 = Integer.parseInt(st.nextToken());
			order[idx1]++;
			order[idx2+idx1]++;
		}
		int sum=0,idx=0;
		for(int i=m-1;i>=0;i--) {
			sum+=order[idx++];
			arr[i][0]=sum;
		}
		for(int i=1;i<m;i++) {
			sum+=order[idx++];
			arr[0][i]=sum;
		}
		for(int i=1;i<m;i++)
			for(int j=1;j<m;j++)
				arr[i][j]=arr[0][j];
		for(int i=0;i<m;i++) {
			for(int j=0;j<m;j++)
				System.out.print(arr[i][j]+1+" ");
			System.out.println();
		}
	}
}