모의 SW 역량테스트 (숫자 만들기, 무선 충전)

[숫자 만들기 - 5644]

 

* 알고리즘

• 브루트포스

 

* 로직

• 연산자의 수만큼 나올 수 있는 모든 경우의 수를 구하면 된다
  
  

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

class Solution
{
    static int N;			//피연산자 카드 개수
	static int[] operation;	//연산자 (+,-,*,/)
	static int[] cards;		//피연산자
	static int max;
	static int min;
    
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int testCase = Integer.parseInt(br.readLine());
		int t=1;
		while(t <= testCase) {
			N = Integer.parseInt(br.readLine());
			operation = new int[4];
			cards = new int[N];
            max = Integer.MIN_VALUE;
			min = Integer.MAX_VALUE;
			
			String input_oper = br.readLine();
			st = new StringTokenizer(input_oper, " ");
			int idx=0;
			while(st.hasMoreTokens()) {
				operation[idx++] = Integer.parseInt(st.nextToken());
			}
			
			String input_cards = br.readLine();
			st = new StringTokenizer(input_cards, " ");
			for(int i=0; i<N; ++i) {
				cards[i] = Integer.parseInt(st.nextToken());
			}
			
			int index=1;
			int acc=cards[0];
			doSolution(index, acc);
			
			System.out.println("#" + t + " " + (max - min));
			t++;
		}
	}
    
    private static void doSolution(int index, int acc) {			
		if(index == N) {
			max = Math.max(max, acc);
			min = Math.min(min, acc);
			return;
		}
		
		for(int i=0; i<4; ++i) {
			if(operation[i] > 0) {
				operation[i]--;
				if(i == 0) {
					doSolution(index+1, acc+cards[index]);	
				} else if(i == 1) {
					doSolution(index+1, acc-cards[index]);
				} else if(i == 2) {
					doSolution(index+1, acc*cards[index]);
				} else if(i == 3) {
					doSolution(index+1, acc/cards[index]);
				}							
				operation[i]++;
			}
		}
	}
}

 

 

[무선 충전 - 5644]

 

* 알고리즘

• BFS
• 브루트포스(가지치기)

 

* 로직

• 무선 충전기 수에 맞게끔 3차원 배열을 설정한다 ex. [APSize][N+1][N+1]
• 사용자(A, B)의 위치를 관리하는 객체와 무선 충전기의 정보를 관리하는 객체를 생성한다
• 각 무선 충전기 종류에 맞게끔 BFS를 통해 배열에 값을 넣는다(여기서 값은 해당 충전기의 performance 값으로)
• 무선 충전기 배열들의 전처리가 끝나면 사용자를 동시에 한칸씩 움직인다
  • 전처리된 각각 무선충전기의 배열의 모든 경우의 수를 구하고
  • A와 B가 이동한 위치에 존재하는 값의 최댓값을 갱신한다
    • 만약 둘다 무선 충전기 범위에 속한 상황에서
      • 같은 무선 충전기라면 -> 절반으로 분할
      • 다른 무선 충전기라면 -> 합산
    • 둘중에 한 개만 무선충전기 범위에 속하면 -> 존재하는 값만
    • 둘다 속하지 않는 경우 -> 0
  • 모든 경우의 수를 거쳐서 나온 최댓값을 result에 누적한다

 

//무선충전
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	
	static int N = 10;
	static int[][][] AP;	
	static int M;		//총 이동시간
	static int APSize;	//무선충전기 개수
	static int[][] operations;	//사용자(A,B)의 명령어
	
	static int[][] directions = {
			{0, -1, 0, 1, 0},
			{0, 0, 1, 0, -1}
	};
	
	static Queue<User_Info> userA;
	static Queue<User_Info> userB;
	static int result;
	
	static class User_Info {
		public int y,x;

		public User_Info(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}	
	}
	
	static class AP_INFO {
		public int y,x;
		public int coverage;
		public int performance;
		
		public AP_INFO(int y, int x, int coverage, int performance) {
			super();
			this.y = y;
			this.x = x;
			this.coverage = coverage;
			this.performance = performance;
		}		
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int testCase = Integer.parseInt(br.readLine());
		int t=1;
		while(t<=testCase) {
			String config = br.readLine();
			st = new StringTokenizer(config, " ");
			M = Integer.parseInt(st.nextToken());
			APSize = Integer.parseInt(st.nextToken());			
			AP = new int[APSize][N+1][N+1];

			//A와 B의 명령어 입력
			operations = new int[2][M+1];
			for(int a=0; a<2; ++a) {
				String input = br.readLine();
				st = new StringTokenizer(input, " ");
				
				int idx=1;
				while(st.hasMoreTokens()) {
					operations[a][idx++] = Integer.parseInt(st.nextToken());
				}
			}
			
			//무선 충전기 입력 받기
			for(int a=0; a<APSize; ++a) {
				String input = br.readLine();
				st = new StringTokenizer(input, " ");
				
				//좌표, 커버, 파워
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int coverage = Integer.parseInt(st.nextToken());
				int performance = Integer.parseInt(st.nextToken());
				
				//해당 무선 충전기 bfs
				AP_INFO apInfo = new AP_INFO(y, x, coverage, performance);
				doBfs(apInfo, a);
			}						
			
			//사용자(A, B) 한칸씩 이동
			userA = new LinkedList<>();
			userB = new LinkedList<>();
			userA.offer(new User_Info(1, 1));
			userB.offer(new User_Info(10, 10));
			
			result = 0;
			for(int j=0; j<=M; ++j) {
				int operA = operations[0][j];
				int operB = operations[1][j];
				
				moveUser(operA, operB);				
			}
			
			System.out.println("#" + t + " " + result);
			t++;
		}

	}

	private static void moveUser(int operA, int operB) {
		User_Info aPos = userA.poll();	//현재 A의 위치
		User_Info bPos = userB.poll();
		
		//A의 움직일 위치
		aPos.y = aPos.y + directions[0][operA];
		aPos.x = aPos.x + directions[1][operA];
		
		//B의 움직일 위치
		bPos.y = bPos.y + directions[0][operB];
		bPos.x = bPos.x + directions[1][operB];					
		
		int max = 0;
		for(int a=0; a<APSize; ++a) {
			for(int b=0; b<APSize; ++b) {
				if(AP[a][aPos.y][aPos.x] > 0 && AP[b][bPos.y][bPos.x] > 0) {
					//a == b라면 -> 절반으로 분할
					if(a == b) {
						max = Math.max(max, AP[a][aPos.y][aPos.x] / 2);
					}
					
					//다르다면 두개의 합으로 갱신
					else {
						max = Math.max(max, AP[a][aPos.y][aPos.x] + AP[b][bPos.y][bPos.x]);
					}
					
				}	
				
                //한쪽만 무선 충전기 범위에 속한 경우
				else if(AP[a][aPos.y][aPos.x] > 0 || AP[b][bPos.y][bPos.x] > 0) {
					max = Math.max(max, AP[a][aPos.y][aPos.x] + AP[b][bPos.y][bPos.x]);
				}
				
				//둘다 무선 충전기 범위에 없는 경우
				else if(AP[a][aPos.y][aPos.x] == 0 && AP[b][bPos.y][bPos.x] == 0) {
					max = Math.max(max, AP[a][aPos.y][aPos.x] + AP[b][bPos.y][bPos.x]);
				}
			}
		}
		
		result += max;
		userA.offer(new User_Info(aPos.y, aPos.x));
		userB.offer(new User_Info(bPos.y, bPos.x));
	}

	private static void doBfs(AP_INFO apInfo, int apIdx) {		
		Queue<AP_INFO> queue = new LinkedList<>();		
		queue.offer(apInfo);
		AP[apIdx][apInfo.y][apInfo.x] = apInfo.performance;
		
		int cover = apInfo.coverage;
		int cycle = 1;
		while(!queue.isEmpty()) {
			if(cycle > cover) break;
			
			int size = queue.size();			
			for(int i=0; i<size; ++i) {
				AP_INFO q = queue.poll();
				
				for(int d=1; d<=4; ++d) {
					int moveY = q.y + directions[0][d];
					int moveX = q.x + directions[1][d];
					
					if(isRanged(moveY, moveX) && AP[apIdx][moveY][moveX] == 0) {
						queue.offer(new AP_INFO(moveY, moveX, cover, q.performance));
						AP[apIdx][moveY][moveX] = q.performance;
					}
				}
			}			
			cycle++;				
		}
	}

	private static boolean isRanged(int y, int x) {
		if(y>=1 && y<=N && x>=1 && x<=N) return true;
		return false;
	}
}