내용

글번호 927
작성자 허진경
작성일 2018-10-26 20:12:00
제목 그래도 시간이 절반은...
내용 그래도 시간이 절반은...
import java.io.FileInputStream;
import java.util.Scanner;

class 그래도시간이절반은
{
	public static void main(String args[]) throws Exception
	{

		//System.setIn(new FileInputStream("input.txt"));

		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = sc.nextInt();
			int K = sc.nextInt();

			int[] W = new int[N];
			int[] S = new int[K];

			for(int i=0; i<N; i++) {
				W[i] = sc.nextInt();
			}
			for(int i=0; i<K; i++) {
				S[i] = sc.nextInt();
			}

//			//입력 데이터 출력
//			for(int i=0; i<N; i++) {
//				System.out.printf("%2d ", W[i]);
//			}
//			System.out.println();
//			for(int i=0; i<K; i++) {
//				System.out.print(S[i] + " ");
//			}
//			System.out.println();
			
			//블록별 마모수준이 가장 큰 값을 저장
			int[][] block_sum = new int[K][N];
			for(int i=0; i<K; i++) {
				for(int j=0; j<=N-S[i]; j++) {
					int max = Integer.MIN_VALUE;
					for(int k=j; k<j+S[i]; k++) {
						if( max < W[k] )
							max = W[k];
					}
					block_sum[i][j] = max;
				}
			}

//			System.out.println("\n블록별 마모 수준");
//			for(int i=0; i<K; i++) {
//				for(int j=0; j<=N-S[i]; j++) {
//					System.out.printf("%2d ", block_sum[i][j]);
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			int min_index = 0;
			int max_wear_level = Integer.MIN_VALUE;
			for(int i=0; i<K; i++) {
				int min_block_wear_level = Integer.MAX_VALUE;
				for(int j=min_index; j<=N-S[i]; j++) {
					if(min_block_wear_level > block_sum[i][j]) {
						min_block_wear_level = block_sum[i][j];
						min_index = i+S[i];
					}
				}
				if(max_wear_level<min_block_wear_level)
					max_wear_level = min_block_wear_level;
//				System.out.printf("-%d %d\n", block[i], min_block_wear_level);
			}
			System.out.println("#"+ test_case + " " + max_wear_level);
		}
		sc.close();
	}
}