[SWEA / 5644번 ] [모의 SW 역량테스트] 무선 충전

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

SW Expert Academy

 

[ 풀이 ] 

시뮬레이션인데 매우 복잡한 시뮬레이션이다.. 

조건에 맞춰 우선순위를 정하고, 이를 계산하는게 힘든거 같다.

풀이코드를 첨부하고, 이후 설명한다. 

[ 풀이 코드 ] 

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

public class 무선충전 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb =new StringBuilder();
		for(int tc =1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken());
			int A = Integer.parseInt(st.nextToken());
			int[] mA = new int[M+1];
			int []mB = new int[M+1];
			StringTokenizer sta = new StringTokenizer(br.readLine());
			StringTokenizer stb = new StringTokenizer(br.readLine());
			for(int i =1; i<= M; i++) {
				mA[i]= Integer.parseInt(sta.nextToken());
				mB[i] = Integer.parseInt(stb.nextToken());
			}
			int[][]AP = new int[A][4];
			for(int i = 0 ; i< A; i++) {
				st = new StringTokenizer(br.readLine());
				AP[i][1] = Integer.parseInt(st.nextToken());
				AP[i][0] = Integer.parseInt(st.nextToken());
				AP[i][2] = Integer.parseInt(st.nextToken());
				AP[i][3] = Integer.parseInt(st.nextToken());
			}//입력 완료 
			Arrays.sort(AP, (a,b)->(b[3]-a[3]));//큰순 정렬 
			int ans =0; 
			int []di =new int[] {0,-1,0,1,0};
			int []dj =new int[] {0,0,1,0,-1};// 이동x, 상,우, 하 좌
			int ai = 1,aj =1;
			int bi = 10,bj=10;
			for(int m =0; m<= M ;m++) {// 이동 
				ai+=di[mA[m]];aj+=dj[mA[m]];
				bi+=di[mB[m]];bj+=dj[mB[m]];
				int aa =-1 ;
				int bb = -2;
				for(int a = 0; a<A; a++) {
					if(AP[a][2]>=(Math.abs(ai-AP[a][0])+Math.abs(aj-AP[a][1]))) {
						aa = a;break;
					}
				}
				for(int b = 0; b<A; b++) {
					if(AP[b][2]>=(Math.abs(bi-AP[b][0])+Math.abs(bj-AP[b][1]))) {
						bb = b;break;
					}
				}
				if(bb==aa) {
					int a = aa+1;
					for(; a<A; a++) {
						if(AP[a][2]>=Math.abs(ai-AP[a][0])+Math.abs(aj-AP[a][1])||AP[a][2]>=Math.abs(bi-AP[a][0])+Math.abs(bj-AP[a][1])) {
							aa = a;
							break;
						}
					}
					if(a==A) {
						ans+=AP[aa][3];
					}else {
						ans+=AP[aa][3];
						ans+=AP[bb][3];
					}
				}else {
					if(aa!=-1)ans+=AP[aa][3];
					if(bb!=-2)ans+=AP[bb][3];
				}
			}
			sb.append('#').append(tc).append(' ').append(ans).append('\n');
		}
		System.out.println(sb);
	}
}

 

이 문제의 핵심은 

 

우선 데이터를 입력 받는다. 

처음 입력받을 떄 헷갈리지 않게 조심하자.. 방향이랑 값이랑

사실 깊게 생각 안하고 뭔가 안맞길래 AP안의 값의 0,1의 순서를 바꿨는데 맞길래 그냥 그렇게 했다

실제로는 di가 반대이겠지..?

그리고 사람 움직임도 받을떄 0을 포함 시켜 주어야 한다. 안움직이는 경우 를 한번에 계산하기 위함이다. 

그리고 이후 반복문을 돌게 된다 

그 전에 P가 큰 순으로 정렬해서 반복문을 한번씩만 돌도록 하자

이동을 하고, 그 다음에 

미리 배열에서 나오지 않을 만한 서로 다른 값을 aa와 bb에 넣어준다. 이 값으로 중복인지 확인할 것이다. 

큰 순서대로 정렬된 AP를 돌면서 

그 안에 포함되어 있으면 aa와 bb에 값을 담아준다. 

그리고 다음에 aa와 bb의 값이 같다면 그 다음에 있는 겹치는 큰 부분을 찾아야 하는데, 

큰 순서대로 정렬해 두었으니, aa+1부터 반복하면 된다(aa+1 이 아니라 aa부터 돌다가 큰 문제가 났었다.. 왜 틀렸는지 한참 고민했다.)

그리고 그 다음 값을 aa에 저장해둔다. (A사람의 최대값 aa인지 B사람의 최대값 bb에 저장해두는거는 중요하지 않다 어짜피 총 합을 ans에 담아줄 것이기 떄문이다. ) 

하지만 만약 다 돌아도 다른 값이 포함되지 않는다면, 

AP[aa][3]에는 하나만 들어가게 된다. ( 모두 짝수이므로 이렇게 처리해도 된다. 만약 홀수라면 나눈다음 더해야 겠다.) 

다른 충전할 곳이 있다면 그 값을 찾아서 ans에 각각 더해주게 된다. 

만약 aa와 bb의 값이 서로 다르고, 초기 값인 -1과 -2와도 다르다면 ans에 값을 각각 더해준다. 

이후 출력해주면 문제는 해결된다.