[SWEA] 5644 - 무선충전

[문제링크]

SW Expert Academy

 

0. 문제는 4사분면같은 x,y좌표를 사용하지만 (+x방향이 오른쪽, +y방향이 아랫쪽)

2차원배열의 인덱스는 아랫쪽-오른쪽의 방향으로 증가하므로, 입력받는 단계에서 x, y를 뒤집어 입력받았다.

 

1. 모든 BC에 대해 A, B 각각 충전 가능 여부를 판단한다

 

2. A 혹은 B 한쪽에만 속하는 BC들의 충전값중 최댓값을 구한다

 

3. A와 B 양쪽에 속하는 BC들의 충전값 중 더 좋은 선택이 있는 경우, A와 B중 작은 충전값을 갱신한다

   - A와 B 충전량의 합계 중 최댓값을 구하는 목적이므로, 동일 BC 접근시 충전량 분배는 고려할 필요 없다

   - A와 B가 300짜리 BC를 공유해 150/150이 되나, A가 독점해 300/0이 되나 합계는 300으로 동일하기 때문이다

 

4. 구해진 A와 B의 최댓값을 누적시켜가며 반복한다

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

public class Solution{
	static int dir[][]=new int[][] {
		{0,0},{-1,0},{0,1},{1,0},{0,-1}
	};
    
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			
			int[] A = new int[] {0,0};
			int[] B = new int[] {9,9};
			
			int[] moveA = new int[n];
			int[] moveB = new int[n];
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < n; i++)	moveA[i]=pint(st.nextToken());
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < n; i++)	moveB[i]=pint(st.nextToken());
			
			int[][] station = new int[m][4];
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine(), " ");
                //x, y swap
				station[i][1]=pint(st.nextToken())-1;
				station[i][0]=pint(st.nextToken())-1;
				station[i][2]=pint(st.nextToken());
				station[i][3]=pint(st.nextToken());
			}
			
			int total=0;
			
			//n초 실행
			for (int i = 0; i <= n; i++) {
				int[][] po = new int[m][2];
				//각 지점별 A,B의 충전가능여부 확인
				for (int j = 0; j < m; j++) {
					if(Math.abs(A[0]-station[j][0])+Math.abs(A[1]-station[j][1]) <= station[j][2] )
						po[j][0]++;
					if(Math.abs(B[0]-station[j][0])+Math.abs(B[1]-station[j][1]) <= station[j][2] )
						po[j][1]++;
				}
				//1인 것들 중 max값 구하기
				int maxA=0, maxB=0;
				for (int j = 0; j < m; j++) {
					if(po[j][0]==1 && po[j][1]==0 && station[j][3]>maxA) {
						maxA=station[j][3];
					}
					if(po[j][0]==0 && po[j][1]==1 && station[j][3]>maxB) {
						maxB=station[j][3];
					}
				}
				
				
				//2인게 존재하고, maxA나 maxB보다 크다면 교체
				for (int j = 0; j < m; j++) {
					if(po[j][1]==1 && po[j][0]==1) {
						if(maxA<=maxB && maxA<station[j][3]) {
							maxA=station[j][3];
						}
						else if(maxB<=maxA && maxB<station[j][3]) {
							maxB=station[j][3];
						}
					}
				}
				
				total+=maxA+maxB;
				
				if(i==n)break;
				else {
					A[0]+=dir[moveA[i]][0];	A[1]+=dir[moveA[i]][1];
					B[0]+=dir[moveB[i]][0];	B[1]+=dir[moveB[i]][1];
				}
			}
			sb.append("#").append(testcase).append(" ").append(total).append("\n");
		}
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

 

채점 결과