고양멍멍이

ㅇ[문제링크]

0. N 범위가 600이므로, O(N^3)까지 실행 가능하다

• O(N^2)로 엘사가 만들 수 있는 모든 눈사람 만들기
• O(N)으로 엘사의 눈사람에 가장 가까운 안나의 눈사람 찾기 (투 포인터 사용)

1. 두 눈덩이를 선택해 엘사의 눈사람을 만든다

• 크기가 큰 아래 눈덩이를 선택하고, 그 다음 위 눈덩이를 선택한다
• 이를 위해 입력값을 크기순으로 정렬해 사용

2. 엘사의 눈사람과 가장 가깝게 안나의 눈사람을 만든다

• 양쪽 끝 눈덩이(가장 큰/가장 작은)를 선택하면서 시작
• 안나의 눈사람이 더 크면 : 더 작아져야 한다 - 큰 눈덩이(위)를 한단계 더 작은 눈덩이로 교체
• 안나의 눈사람이 더 작으면 : 더 커져야한다 - 작은 눈덩이(아래)를 한단계 더 큰 눈덩이로 교체
• 두 눈사람의 크기가 같아지거나 / 안나의 눈사람의 위/아래 눈덩이가 교차하면 종료

3. 안나의 눈사람마다 갱신한 min값이 정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int[]snow=new int[N];
		int min=Integer.MAX_VALUE;
		
		for (int i = 0; i < N; i++) {
			snow[i]=pint(st.nextToken());
		}
		
		Arrays.sort(snow);
		
		for (int elsaFst = 0; elsaFst < N; elsaFst++) {
			//아래쪽
			for (int elsaSnd = 0; elsaSnd < elsaFst; elsaSnd++) {
				//위쪽
				int elsaSnow = snow[elsaFst]+snow[elsaSnd];
				int fst=0,snd=N-1;
				
				//안나의 눈사람이 더 크면 - snd를 줄인다
				//더 작으면 - fst를 늘린다
				
				while(fst<snd) {
					if(fst==elsaFst || fst==elsaSnd) {
						fst++;continue;
					}

					if(snd==elsaFst || snd==elsaSnd) {
						snd--;continue;
					}
					
					int annaSnow = snow[fst]+snow[snd];
					min=Math.min( min, Math.abs(annaSnow-elsaSnow) );
					
					if(annaSnow>elsaSnow) {
						snd--;
					}
					if(annaSnow<elsaSnow) {
						fst++;
					}
					if(annaSnow==elsaSnow) {
						break;
					}
					
					
				}
				
			}
		}
		
		System.out.println(min);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. N명의 학생들 중 K명을 선택했을때, 모든 학생들이 친구여야 한다

  - 아무나 두 명 뽑더라도 이 둘은 항상 친구여야 한다

1. 재귀적으로 이전에 선택한 X와 친구인 Y로 진행하되, 지금까지 선택해온 사람들 전부와 Y가 친구일때만 진행한다

2. 목표인 K명에 도달하면 완성, 종료한다

  - 가능한 학생 번호가 작은 결과를 내야 하므로, 번호가 작은 학생부터 시작한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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(), " ");
		k = pint(st.nextToken());
		n = pint(st.nextToken());
		f = pint(st.nextToken());
		
		picked = new int[k];
		
		adj = new boolean[n+1][n+1];
		Arrays.fill(adj[0], true);
		
		friendCnt=new int[n+1];
		friendCnt[0]=n;
		
		for (int i = 0; i < f; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int p1 = pint(st.nextToken());
			int p2 = pint(st.nextToken());
			
			adj[p1][p2]=true; friendCnt[p1]++;
			adj[p2][p1]=true; friendCnt[p2]++;
		}
		
		if(rec(0,0)) {
			for (int i = 0; i < k; i++) {
				System.out.println(picked[i]);
			}
		}
		else {
			System.out.println(-1);
		}
	}
	
	static int k,n,f;
	static boolean[][]adj;
	static int[] friendCnt;
	static int[] picked;
	
	static boolean rec(int cnt, int cur) {
		if(cnt==k) {
			return true;
		}
		//현재 cur의 친구를 다 반영해도 k가 안되면 탈출
		if(friendCnt[cur]< k-cnt)return false;
		
		for (int i = 1; i <= n; i++) {
			if(adj[cur][i]) {
				//i번째 사람와 친구
				boolean isF=true;
				for (int j=0; j<cnt; j++) {
					if(!adj[ picked[j] ][i]) {
						isF=false;
						break;
					}
				}
				//지금까지 찾은 모든 친구와 i도 친구면
				if(isF) {
					picked[cnt]=i;
					if(rec(cnt+1,i))return true;
					
				}
			}
			
		}
		
		return false;
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 12개의 숫자로 육각성을 완성했을때, 모든 변의 합이 26으로 같아야 한다

1. brute-force로 진행시 12! = 479001600의 가짓수

• 1초 시간제한 내 풀이 불가능

2. 모든 변을 완성시키지 말고, 완성되는대로 검사한다

• 위-왼쪽부터 차례대로 채워나갈 경우, 5개의 숫자를 선택하면 윗 변 하나가 완성된다
• 해당 변의 합이 26일 경우에만 진행

3. 사전순으로 가장 앞서는 결과를 출력해야하므로, 작은 수부터 큰 수로 진행하며 하나라도 성공하면 종료, 반환한다

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));
        StringBuilder sb;


        num = new int[12];
        isUsed = new boolean[12]; 
        int idx=0;

        String[] input = new String[5];

        for (int i = 0; i < 5; i++) {

            input[i] = br.readLine();

            for (int j = 0; j < input[i].length(); j++) {
                if(input[i].charAt(j)=='x')num[idx++]=0;
                else if(input[i].charAt(j)!='.') {
                    num[idx]= input[i].charAt(j)-'A'+1;
                    isUsed[num[idx++]-1]=true;
                }
            }
        }

        String s = rec(0);
        idx=0;
        for (int i = 0; i < 5; i++) {
            sb=new StringBuilder(input[i]);

            for (int j = 0; j < sb.length(); j++) {
                if(sb.charAt(j)!='.') {
                    sb=sb.replace(j, j+1, ""+s.charAt(idx++));
                }
            }
            System.out.println(sb);
        }

    }

    static boolean[] isUsed;
    static int[] num;

    static String rec(int idx) {
        String s="";

        if(idx==5) {
            if(num[1]+num[2]+num[3]+num[4] != 26)return null;
        }
        else if(idx==8) {
            if(num[0]+num[2]+num[5]+num[7] != 26)return null;
        }
        else if(idx==11) {
            if(num[0]+num[3]+num[6]+num[10] != 26)return null;
            if(num[7]+num[8]+num[9]+num[10] != 26)return null;
        }
        else if(idx==12) {
            if(num[1]+num[5]+num[8]+num[11] != 26)return null;
            if(num[4]+num[6]+num[9]+num[11] != 26)return null;
            for (int i = 0; i < num.length; i++) {
                s+=(char)(num[i]+'A'-1);
            }
            return s;
        }

        if(num[idx]!=0) {
            return rec(idx+1);//이미 초기에 숫자가 있었다면 
        }
        else {
            for (int i = 0; i < 12; i++) {
                if(!isUsed[i]) {
                    //사용한적 없으면
                    num[idx]=i+1;
                    isUsed[i]=true;

                    if( (s = rec(idx+1)) != null ) {
                        return s;
                    }

                    num[idx]=0;
                    isUsed[i]=false;
                }
            }
        }
        return null;
    }

    static int pint(String s) {
        return Integer.parseInt(s);
    }

}

[문제링크]

0. 백트래킹의 국룰문제

1. n번째 행에 대해 1~n-1행의 퀸 위치와 충돌하지 않는 모든 열들을 놓아보면서 진행한다

2. 모든 행에 성공적으로 퀸이 놓아졌다면 성공 카운트 + 1

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));
		
		int N = pint(br.readLine());
		
		pos = new int[N];
		ans=0;
		
		rec(0);
		System.out.println(ans);
		
	}
	static int ans;
	static int[] pos;
	
	static void rec(int row) {
		if(row==pos.length) {
			ans++;
			return;
		}
		
		for (int i = 0; i < pos.length; i++) {
			if(isOK(row, i)) {
				pos[row]=i;
				rec(row+1);
			}
		}
	}

	static boolean isOK(int row, int i) {
		for (int j = 1; j <= row; j++) {
			if(pos[row-j]==i)return false;
			if( Math.abs(pos[row-j]-i) == j)return false;
		}
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

[문제링크]

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. x와 y 슬라임으로, x+y 슬라임을 만들며, x*y 점수를 획득한다

1. N번째 합칠 슬라임의 무게가 y였다면, N+1, N+2...번째 연산에도 y가 포함되게 된다

2. 크기가 큰 슬라임을 빠르게 합쳐, 이후 연산들에 최대한 많이 포함되도록 해야 한다 (그리디)

3. 슬라임을 크기순으로 2개씩 꺼내며 합쳐나간다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
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<>();
		
		int N = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			pq.offer(pint(st.nextToken()));
		}
		
		int score = 0;
		while(pq.size()!=1) {
			int fst = pq.poll();
			int snd = pq.poll();
			score+=fst*snd;
			pq.offer(fst+snd);
			
		}
		
		System.out.println(score);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}