고양멍멍이

[문제링크]

0. 위 그림과 같이 높이를 하나씩 받으며 스택에 저장하고, 해당 입력으로 인해 발생한 빗물 공간을 구해 누적한다

1. 입력 x가 들어왔을때, 스택에 자기보다 작은 값이 있다면, 빗물 공간이 발생할 수 있다

• 위 그림처럼 6 0 4 0 3 0 0 5 순으로 입력이 들어왔을때, 3과 5 사이에는 공간이 발생한다 (빨강)
• 그 다음 4와 5 사이에도 공간이 발생했는데, 이전에 3까지의 높이는 처리했으므로 4 높이에 대해서만 공간이 생긴다 (노랑)
• 이전에 처리한 높이를 prevCnt로 저장, 사용한다
• 공간이 계속해 발생할 수 있으므로, 스택을 계속 따라간다

2. 스택에 자기보다 큰 값이 있다면, 역시 공간이 발생할 수 있다

• 6과 4 사이에서 공간이 발생한다 (파랑)
• 이때 생성되는 공간의 높이는 입력 x에서 이전 처리값 prevCnt를 뺀 값이다
  • 위 그림에서 초록색 부분은, 입력 x는 5이고 prevCnt는 4이므로 높이는 1이다
• 자기보다 큰 값을 만났으므로, 공간이 계속해서 발생할 수 없으니 종료한다

3. 위 방식으로 공간의 높이는 구할 수 있다

• 공간의 너비를 구하기 위해, 스택에 저장할 때 값뿐 아닌 해당 지점의 x좌표도 함께 저장한다
• 두 좌표를 비교해 너비를 구하여, 높이와 곱해 총 빗물 공간의 면적을 구한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
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(), " ");
		int H = pint(st.nextToken());
		int W = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		Stack<int[]> stack = new Stack<>();
		int area=0;
		
		for (int i = 0; i < W; i++) {
			int input = pint(st.nextToken());
			
			int prevMax=0, sum=0;
			while(!stack.isEmpty() && stack.peek()[0]<=input) {
				int[] tmp = stack.pop();
				
				if(tmp[0]>prevMax) {
					int height = tmp[0]-prevMax;
					prevMax=tmp[0];
					sum+= height*( i-tmp[1]-1 );
				}
				
			}
			
			if(!stack.isEmpty()) {
				int[] tmp = stack.peek();
				int height = input - prevMax;
				sum+= height*(i-tmp[1]-1);
			}
			
			area+=sum;
			// 스택에 넣기
			stack.add(new int[] {input,i});
			
		}
		System.out.println(area);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 번갈아가며 양쪽 끝에서 한장씩 집을때 최대한 많은 점수를 얻는 방법

1. x~y까지의 카드에서 최대한 많은 점수를 얻으려면 card[y] + (x~y-1) 혹은 card[x] + (x+1~y)중 큰 값으로 고를 수 있다

2. 이때, 각자 서로의 점수를 위해 최선의 전략을 사용하고, 서로 가져갈수 있는 카드의 총합은 동일하다

• 따라서, 후 플레이어의 최선의 전략 = 선 플레이어의 점수를 가능한 낮추는 전략 과 같다

3. DP테이블을 2중으로 만들어, (x, y) 만큼의 카드 상태에서 선 플레이어/후 플레이어 각각의 최선의 결과를 저장한다

• 후 플레이어의 선택은 선 플레이어의 점수와는 관계없으므로 저장하지 않는다

4. 모든 테이블이 완성된 후, 모든 카드에 대해 선 플레이어의 점수를 출력한다

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));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] card = new int[N];
			int[][][]dp = new int[N+1][N+1][2];
			
			for (int i = 0; i < N; i++) {
				card[i]=pint(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				dp[i][i][0]=card[i];
				dp[i][i][1]=0;
			}
			
			//i~i+len 까지의 카드를 고려했을때, 근우가 얻을수 있는 최대 점수
			for (int len = 1; len < N; len++) {
				
				for (int i = 0; i < N-len; i++) {
					//i : 시작점, len : 길이
					int j = i+len;
					//근우턴일때 근우 최대점수 = 왼/오 각 경우중 최댓값 + 카드 선택값
					dp[i][j][0]=Math.max(card[j]+dp[i][j-1][1], card[i]+dp[i+1][j][1]);
					//명우턴일때 근우 최대점수 = 왼/오 각 경우중 최솟값 (카드 선택 못함)
					dp[i][j][1]=Math.min(dp[i+1][j][0], dp[i][j-1][0]);
				}
			}
			System.out.println(dp[0][N-1][0]);			
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 두 상자에 x,y개의 구슬이 있고, b1,b2,b3 중 하나만큼 구슬을 꺼낼 수 있을때, 최종 승자를 찾는 문제

1. (x, y)에서 시작해 b1, b2, b3를 빼는 경우의 수 전체를 고려했을때, 단 하나라도 승리하는 경우가 있다면 승리한다

2. 반대로, 모든 경우의 수가 패배라면, 패배한다

3. 선제공격이 이기는 경우를 true, 지는 경우를 false로 둔다

4. 최소 선택 단위인 b1보다 구슬의 수가 적다면 선택할수 없으므로 패배한다, 이를 기초로 DP 진행

5. 선공인 A가 어떠한 선택을 하여 구슬 상태가 (x', y')로 변했는데, DP[x'][y']가 선공 승리인 상태라면, A는 패배한다

• (x', y')상태에서는 턴이 넘어가 B가 선공이 되기 때문
• 즉, DP[x'][y']로 진행할 경우 현재 상태인 DP[x][y]에서의 결과는 !DP[x'][y']가 된다

6. DP 테이블이 완성되면 구한 결과 출력

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(), " ");
		int b1 = pint(st.nextToken());
		int b2 = pint(st.nextToken());
		int b3 = pint(st.nextToken());
		
		boolean[][]dp = new boolean[501][501];
		
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {
				if(i>=b1&&j>=b1) {
					//어떤 선택을 하더라도 상대 승리
					if(dp[i-b1][j] && dp[i][j-b1])dp[i][j]=false;
					//내가 이기는 선택지가 존재
					else dp[i][j]=true;
				}
				else if(i>=b1)dp[i][j]=!dp[i-b1][j];
				else if(j>=b1)dp[i][j]=!dp[i][j-b1];

				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b2&&j>=b2) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b2][j] && dp[i][j-b2])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b2)dp[i][j]=!dp[i-b2][j];
					else if(j>=b2)dp[i][j]=!dp[i][j-b2];
				}
				
				//위에서 결정되지 않았을 경우에만
				if(!dp[i][j]) {
					if(i>=b3&&j>=b3) {
						//어떤 선택을 하더라도 상대 승리
						if(dp[i-b3][j] && dp[i][j-b3])dp[i][j]=false;
						//내가 이기는 선택지가 존재
						else dp[i][j]=true;
					}
					else if(i>=b3)dp[i][j]=!dp[i-b3][j];
					else if(j>=b3)dp[i][j]=!dp[i][j-b3];
				}
			}
		}
		 
		for (int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int k1 = pint(st.nextToken());
			int k2 = pint(st.nextToken());
			
			System.out.println(dp[k1][k2]?'A':'B');
			
		}
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. n글자 이내로 이루어진 가장 긴 연속된 문자열 찾기

• 투 포인터로 n글자를 유지하면서 진행한다

1. n+1글자가 되어 읽을 수 없을때까지 snd 포인터를 진행, 문자열을 늘린다

• 최장 문자열 길이를 갱신한다

2. 다시 n글자가 되어 읽을 수 있을때까지 fst 포인터를 진행, 문자열을 줄인다

3. snd가 끝에 도달하여 종료되었을때, 가장 길었던 문자열의 길이가 정답

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());
		String s = br.readLine();
		
		int maxLen=0;
		int len = 0;
		int[] cnt = new int[26];
		int kindCnt=0;
		
		int fst=0, snd=0;
		
		while(fst<=snd && snd<s.length()) {
			//1. N글자+1까지 snd 늘리면서 len 비교저장
			while(snd<s.length() && kindCnt<=N) {
				int cur = s.charAt(snd++)-'a';
				if(cnt[cur]==0)kindCnt++;
				cnt[cur]++;
				len++;
				//N+1글자일 때는 len을 갱신하면 안된다 
				if(kindCnt<=N)maxLen=Math.max(maxLen, len);
			}
			//2. N글자까지 fst 줄이기
			
			while(fst<=snd && kindCnt>N) {
				int cur = s.charAt(fst++)-'a';
				cnt[cur]--;
				if(cnt[cur]==0)kindCnt--;
				len--;
			}
			
		}
		System.out.println(maxLen);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

ㅇ[문제링크]

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);
	}
	
}