고양멍멍이

[문제링크]

0. 과제 문제와 거의 동일한 문제 (링크)

1. N일까지인 강연을 N-1일에는 갈 수 있지만, N+1일에 가는것은 불가능하다

2. 가능한 마지막날부터 시작해 탐색하며, 그날그날 최고 보수의 강의를 선택한다

3. 과제 문제와 달리 강의 의뢰가 아예 들어오지 않을 수 있으므로, (0, 0)인 가상의 과제를 만들어 제공한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		
		int[][] recture = new int[N+1][2];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			recture[i][0]=pint(st.nextToken());
			recture[i][1]=pint(st.nextToken());
		}
		
		Arrays.sort(recture, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[1]-o1[1];
			}
		});
		
		int day = recture[0][1];
		int i=0;
		int money=0;
		PriorityQueue<Integer>pq = new PriorityQueue<>(Collections.reverseOrder());
		
		while(day!=0) {
			while(i<recture.length && recture[i][1]==day) {
				pq.add(recture[i][0]);
				i++;
			}
			day--;
			if(!pq.isEmpty())money+=pq.poll();
		}
		System.out.println(money);
		
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 먼저 선택한 카드 묶음은 이후 연산들에도 반영된다

  - 큰 카드 묶음 선택을 최대한 뒤로 미뤄야한다

1. 우선순위 큐에 모든 카드를 넣어 오름차순 정렬처럼 작업한다

2. 당장 가장 작은 두 카드를 합쳐 묶음으로 만든 후, 다시 큐에 넣어 데이터 재정렬

3. 1~2를 큐에 최종 카드 묶음 하나만 남을때까지 반복한다

4. 지금까지 누적한 카드 묶음 갯수가 답

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer>pq = new PriorityQueue<>();
		
		int N = pint(br.readLine());
		for (int i = 0; i < N; i++)pq.offer(pint(br.readLine()));
		
		int count=0;
		while(pq.size()!=1) {
			int fst = pq.poll();
			int snd = pq.poll();
			count+=fst+snd;
			pq.offer(fst+snd);
		}
		System.out.println(count);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 최소 횟수로 목적지까지 도달하기 = 가능한 연료가 많은 주유소만 이용하기

1. 초기 이동가능 거리 X 안에 있는 주유소를 탐색

2. 우선순위 큐를 이용해 연료가 가장 많은 주유소를 선택, X를 X'로 갱신

3. X'로 거리가 늘어나며 추가로 갈 수 있게 된 주유소를 탐색

4. 1~3번 과정을 반복한다. X거리가 목표 거리를 초과하면 도달 성공

  - 더이상 주유소가 없는데 목표 거리에 도달하지 못하면 도달 실패

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer>pq=new PriorityQueue<>(Collections.reverseOrder());
		
		int N = pint(br.readLine());
		int[][] oil = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			oil[i][0] = pint(st.nextToken());
			oil[i][1] = pint(st.nextToken());
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int dest = pint(st.nextToken());
		int fuel = pint(st.nextToken());
		int count=0;
		int idx=0;
		
		Arrays.sort(oil, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[0]-o2[0];
			}
		});
		
		while(fuel<dest) {
			while(idx<oil.length && oil[idx][0]<=fuel) {
				pq.offer(oil[idx++][1]);
			}
			
			if(pq.isEmpty()) {
				count=-1; break;
			}
			else {
				count++;
				fuel+=pq.poll();
			}
		}
		System.out.println(count);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 일반적인 냅색의 DP해결법을 적용하면 최대 100개의 물건에 대해 - 최대 10000000의 메모리를 고려해야 한다

  - 시간, 공간복잡도 둘 다 문제가 생긴다

  - 시간 복잡도 O(NM) = 10억

  - 공간 복잡도 O(2M) = 80Mb

1. 모든 가능한 메모리 값에 대해 최소 비활성화 cost를 구하는게 아닌, 모든 가능한 cost값에 대해 최대 확보 메모리를 구한다

2. cost는 1~100이므로, 시간/공간 복잡도 문제 없음

3. 일반적 냅색처럼 DP로 하나씩 추가해 나간다

4. 확보 메모리 M이 가능한 최소 cost를 구하는게 목적이므로, 최종 DP결과를 오름차순으로 탐색하며 최초로 M 이상 확보된 순간이 정답

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = pint(st.nextToken());
		M = pint(st.nextToken());
		
		memory=new int[N];
		cost=new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			memory[i]=pint(st.nextToken());
		}
		
		int totalCost=0;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			cost[i]=pint(st.nextToken());
			totalCost+=cost[i];
		}
		
		int[] dpCur = new int[totalCost+1];
		int[] dpPrev = new int[totalCost+1];
		for (int i = 0; i < N; i++) {
			//i번째 물건을 고려했을때
			for (int j = 0; j < dpPrev.length; j++) {
				if(j<cost[i])dpCur[j]=dpPrev[j];
				else dpCur[j] = Math.max(dpPrev[j], dpPrev[j-cost[i]] + memory[i]);
			}
			dpPrev = dpCur.clone();
		}
		
		for (int i = 0; i < dpCur.length; i++) {
			if(dpCur[i]>=M) {
				System.out.println(i);
				break;
			}
		}
		
		
	}
	static int minCost, N, M;
	static int[] memory;
	static int[] cost;
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 센서의 위치가 아닌, 센서 사이의 거리에 대한 문제이다

1. 센서가 N개 있다면, 센서 사이의 거리는 N-1개 생성된다

2. 기지국이 1개라면, 해당 기지국은 모든 거리를 포함해야한다

3. 기지국이 2개라면, 어떤 거리 X를 이루는 두 센서를 각각 관리함으로서, 거리 X부분을 포함하지 않아도 된다

4. 기지국이 K개라면, N-1개의 거리들 중 K-1개를 선택하지 않아도 된다

5. 전체 거리들 중 그 값이 큰 순서로 K-1개 선택하지 않으면 요구한 최소 길이의 합이 나온다

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int K = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int minimumArea=0;
		
		int[] sensor = new int[N];
		PriorityQueue<Integer>pq = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			sensor[i] = pint(st.nextToken());
		}
		
		Arrays.sort(sensor);
		
		for (int i = 1; i < N; i++) {
			int distance = sensor[i]-sensor[i-1];
			pq.add(distance);
		}
		
		
		for (int i = 0, len=pq.size(); i < len - (K-1); i++) {
			minimumArea+=pq.poll();
		}
		System.out.println(minimumArea);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. PPAP문자열이란? - P에서 시작해 P를 PPAP로 치환한 문자열

  - 반대로 PPAP를 P로 치환하다 보면 근본인 P로 돌아간다

1. PPAP는 P로만 치환되므로, A에만 집중하면 된다

2. A가 들어왔을때, 앞에는 반드시 P가 2개 이상 존재해야하고, 뒤에도 P가 하나 존재해야만 한다

3. 해당 조건을 위해, 앞에 등장한 P의 갯수를 세서 저장하고 있는다 (curIndex)

  - A가 들어올 때 curIndex가 2 이상이고, A의 뒤에도 P가 있다면 PPAP를 감지, P로 치환한다

  - 결과적으로 curIndex는 (-2+1) 되니 -1 된다

4. 해당 조건을 만족하지 않을 경우 PPAP문자열이 아니므로, 즉시 실패처리 및 break한다

5. 모든 PPAP가 성공적으로 전환된 후에, P 하나만 남아있어야한다

  - curIndex이 1보다 크면 P가 여러개 있는 문자열, 실패처리한다

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		
		int curIndex=0;
		boolean isOK=true;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			if(c=='P') {
				curIndex++;
			}
			else {
				//new PPAP or wrong
				if(c=='A') {
					if(curIndex>=2 && i+1 < s.length() && s.charAt(i+1)=='P') {
						curIndex--;
						i++;
					}
					else {
						//wrong
						isOK=false;
						break;
					}
				}
				else {
					//wrong
					isOK=false;
					break;
				}
			}
		}
		if(curIndex>1)isOK=false;
		System.out.println(isOK?"PPAP":"NP");
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 마감일까지 10일남은 과제를 오늘 하는건 괜찮지만, 마감일까지 하루 남은 과제를 10일뒤에 하는것은 불가능하다

  - 가장 먼 마감일부터 그리디하게 최고 점수의 과제를 선택한다

1. 과제를 마감일 내림차순으로 정렬한다

2. 최고 점수의 과제를 빠르게 선택하기 위해 priority queue 사용

3. 각 날짜별로, 해당 날짜 마감의 과제를 priority queue에 넣고, 최고 점수의 하나만 꺼내서 누적한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int[][]assign = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			assign[i][0] = pint(st.nextToken());
			assign[i][1] = pint(st.nextToken());
		}
		
		Arrays.sort(assign, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[0]-o1[0];
			}
		});
		
		PriorityQueue<Integer>pq = new PriorityQueue<>(Comparator.reverseOrder());
		int totalScore=0;
		
		int today = assign[0][0];
		int i=0;
		while(today!=0) {
			while(i<N && assign[i][0]==today) {
				pq.add(assign[i][1]);
				i++;
			}
			
			//날짜 갱신
			today--;
			if(!pq.isEmpty())totalScore+=pq.poll();
		
		}
		
		System.out.println(totalScore);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

0. 팰린드롬 수인지 판단하기 : 앞/뒤 양쪽에서 동시에 출발해, 한칸씩 이동하며 수가 같은지 비교

  - 거의 O(1)에 가까운 복잡도를 가진다

1. 에라토스테네스의 체를 이용해 소수를 판별하면서, 소수에 대해서만 팰린드롬 여부를 판단한다

2. 입력 값 이상의 소수&팰린드롬이 발견되면 소수 판별을 종료하고, 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int range=2000000;
		int ans=0;
		boolean[] notPrime = new boolean[range];
		for (int i = 2; i < range; i++) {
			if(!notPrime[i]) {
				for (int j = i; j < range; j+=i) {
					notPrime[j]=true;
				}
				if(isPalin(i)) {
					if(i>=N) {
						ans=i;
						break;
					}
				}
			}
		}
		System.out.println(ans);
		
	}
	static boolean isPalin(int n) {
		String str = Integer.toString(n);
		int s = 0, e = str.length()-1;
		
		while(s<=e) {
			if(str.charAt(s++)!=str.charAt(e--)) {
				return false;
			}
		}
		return true;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}