문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98+sw&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

코드 (Java)

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

class Solution
{
	private static final int X = 0;
	private static final int Y = 1;
	private static final int C = 2;
	private static final int P = 3;
	private static final int[][] delta = {{0, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 0}};
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			//metadata setup
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			int M = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int[] route1 = new int[M+1];
			int[] route2 = new int[M+1];
			int p1X = 1, p1Y = 1, p2X = 10, p2Y = 10;
			int[][] BCInfo = new int[A][4];
			boolean[] near1 = new boolean[A];
			boolean[] near2 = new boolean[A];
			
			st = new StringTokenizer(br.readLine().trim());
			for (int i = 1; i <= M; ++i) {
				route1[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine().trim());
			for (int i = 1; i <= M; ++i) {
				route2[i] = Integer.parseInt(st.nextToken());
			}
			
			for (int i = 0; i < A; ++i) {
				st = new StringTokenizer(br.readLine().trim());
				for (int j = 0; j < 4; ++j) {
					BCInfo[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int maxCharge = 0;
			
			for (int iter = 0; iter <= M; ++iter) {
				int maxChargeIter = 0;
				p1X += delta[route1[iter]][X];
				p1Y += delta[route1[iter]][Y];
				p2X += delta[route2[iter]][X];
				p2Y += delta[route2[iter]][Y];
				
//				System.out.printf("p1X : %d, p1Y : %d, p2X : %d, p2Y : %d\n", p1X, p1Y, p2X, p2Y);
				
				for (int bidx = 0; bidx < A; ++bidx) {
					if (Math.abs(p1X - BCInfo[bidx][X]) + Math.abs(p1Y - BCInfo[bidx][Y]) <= BCInfo[bidx][C]) {
						near1[bidx] = true;
					} else {
						near1[bidx] = false;
					}
				}
				
				for (int bidx = 0; bidx < A; ++bidx) {
					if (Math.abs(p2X - BCInfo[bidx][X]) + Math.abs(p2Y - BCInfo[bidx][Y]) <= BCInfo[bidx][C]) {
						near2[bidx] = true;
					} else {
						near2[bidx] = false;
					}
				}
				
				for (int p1Idx = 0; p1Idx < A; ++p1Idx) {
					for (int p2Idx = 0; p2Idx < A; ++p2Idx) {
						int maxChargeComb = 0;
						if (near1[p1Idx]) {
							maxChargeComb += BCInfo[p1Idx][P];
						}
						if (near2[p2Idx] && (!near1[p1Idx] || p1Idx != p2Idx)) {
							maxChargeComb += BCInfo[p2Idx][P];
						}
						
						maxChargeIter = Math.max(maxChargeIter, maxChargeComb);
					}
				}
				
//				System.out.printf("iter : %d, maxChargeIter : %d\n", iter, maxChargeIter);
				
				maxCharge += maxChargeIter;
			}
			
			bw.write("#" + test_case + " " + maxCharge + "\n");
		}
		bw.flush();
		bw.close();
	}
}

풀이

• 구현 + 브루트포스

• 모든 경우를 고려해도 수행해야하는 연산이 테스트케이스당 최악의 경우 100 x 8 x 2 x 64 = 대략 10000번밖에 안되서 브루트포스 형식으로 풀었다.