고양멍멍이

[문제링크]

0. 1019번, 책 페이지의 코드 재사용 (링크)

1. 두 페이지까지의 숫자를 구해 합을 구하고, 그 차이를 구한다

  - L페이지는 포함되야 하므로, 따로 합해준다

* SWEA 5604번 구간합 문제와 거의 동일하다 (링크)

  - 출력 양식 수정 후 반복문만 돌리면 통과

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		String n = st.nextToken();
		String m = st.nextToken();
		long temp = page(m)-page(n);
		for (int i = 0; i < n.length(); i++)temp+=n.charAt(i)-'0';
		System.out.println(temp);
	}
	
	static long page(String N) {
		long returnVal=0;
		long[]page = new long[10];
		long[]prev = new long[10];
		long[]ans = new long[10];

		int len = N.length();
		
		ArrayList<long[]>index=new ArrayList<>();
		index.add(page.clone());
		long cnt=1;
		//전처리
		for (int i = 0; i <= len; i++) {
			for (int j = 0; j <= 9; j++) {
				page[j]*=10;
				page[j]+=cnt;
			}
			index.add(page.clone());
			cnt*=10;
		}
		
		//0번 자리부터
		for (int i = 0; i < N.length(); i++, len--) {
			int cur = N.charAt(i)-'0';

			long[] curIdx = index.get(len-1);
			long repeat = (long)Math.pow(10, len-1);
			for (int j = 0; j <= 9; j++) {
				ans[j]+=curIdx[j]*cur;
				ans[j]+=prev[j]*repeat*cur;//prev처리
			}
			
			//가장 앞자리 처리
			for (int j = 0; j < cur; j++) {
				ans[j]+=repeat;
			}
			
			prev[cur]++;
		}
		for (int j = 0; j <= 9; j++) ans[j]+=prev[j];
		for (int i = 0; i < N.length(); i++) ans[0]-=Math.pow(10, i);
		for (int i = 0; i <= 9; i++) {
			returnVal+=i*ans[i];
		}
		return returnVal;
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. state 클래스로 정보를 관리 (x좌표, y좌표, 이전이동, 이동횟수)

1. bfs처럼 진행하되, 항상 목표지점으로 다가가는 이동이 최적의 이동이다

  - 현재 좌표와 목표좌표를 비교, 나아가야 할 방향을 결정한다

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

public class Solution{
	
	static class state {
		public int x,y,prev,cost;
		public state(int x, int y, int prev, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.prev = prev;
			this.cost = cost;
		}
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int sx = pint(st.nextToken());
			int sy = pint(st.nextToken());
			int dx = pint(st.nextToken());
			int dy = pint(st.nextToken());
			
			Queue<state>qu=new LinkedList<>();
			
			if(sx==dx && sy==dy) {
				sb.append("#").append(testcase).append(" ").append(0).append("\n");
				continue;
			}
			
			if(sx<dx)qu.offer(new state(sx+1,sy,1,1));
			else qu.offer(new state(sx-1,sy,1,1));
			if(sy<dy)qu.offer(new state(sx,sy+1,2,1));
			else qu.offer(new state(sx,sy-1,2,1));
			
			while(true) {
				state cur = qu.poll();
				System.out.println(cur.x+" "+cur.y);
				if(cur.x==dx && cur.y==dy) {
					sb.append("#").append(testcase).append(" ").append(cur.cost).append("\n");
					break;
				}
				
				if(cur.prev==2) {
					if(cur.x<dx)qu.offer(new state(cur.x+1, cur.y, 1, cur.cost+1));
					else qu.offer(new state(cur.x-1, cur.y, 1, cur.cost+1));
				}
				else {
					if(cur.y<dy)qu.offer(new state(cur.x, cur.y+1, 2, cur.cost+1));
					else qu.offer(new state(cur.x, cur.y-1, 2, cur.cost+1));
				}
				
			}
		}System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 가장 먼 점이 원점으로 이동할 때까지, 먼저 원점에 도달한 점들은 +1 -1 운동을 반복하게 된다

  - 모든 점들의 2로 나눈 나머지가 같지 않다면, 점들의 움직임이 일치하지 않아 한 점으로 모이는게 불가능하다

1. 입력받으며, 모든 수가 홀수 or 짝수로 통일되있는지 확인한다

  - 통일되있지 않으면, -1을 출력

2. 동시에, 입력값중 최댓값을 탐색한다

  - 모든 값이 홀/짝수로 통일되 있다면, 최댓값이 원점에 도달하는 순간 종료된다

3. 매 초 이동량의 누적값을 구하여 그 값이 max보다 크면서 max와의 차이가 짝수일 때 종료한다

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

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[] len = new int[N];
			int sum=0;
			int cnt=0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			len[0]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
			int max=len[0];
			for (int i = 1; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				len[i]= Math.abs(pint(st.nextToken())) + Math.abs(pint(st.nextToken()));
				max=Math.max(max, len[i]);
				if(len[i]%2 != len[i-1]%2) {
					cnt=-1;
				}
			}
			
			if(cnt==0) {
				while(true) {
					boolean isE=true;
					if(sum<max || (max-sum)%2!=0) {
						isE=false;
					}
					if(isE)break;
					sum+=++cnt;
				}
			}
			sb.append("#").append(testcase).append(" ").append(cnt).append("\n");
			
		}System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 1967번 문제와 거의 동일한 풀이 (링크)

1. 트리의 모든 노드를 거치며 최댓값을 찾으므로, 시작점의 위치는 아무거나 선택해도 상관 없다

2. 부모-자식 관계를 확인하기 힘드므로 boolean배열을 유지해 방문 노드의 재방문을 막는다

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		isV=new boolean[N+1];
		graph=new ArrayList<>();
		max=0;
		
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int V = pint(st.nextToken());
			int node=0;
			while( (node=pint(st.nextToken()))!=-1 ) {
				int cost = pint(st.nextToken());
				graph.get(V).add(new int[] {node,cost});
			}
		}

		rec(1);
		System.out.println(max);
		
	}
	static int N, max;
	static boolean[]isV;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		isV[node]=true;
		int fst=0,snd=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] next = graph.get(node).get(i);
			//미방문이면
			int temp=0;
			if(!isV[ next[0] ]) {
				temp = next[1] + rec( next[0] );
			}

			if(fst<temp) {
				snd=fst;
				fst=temp;
			}else if(snd<temp) {
				snd=temp;
			}
		}
		
		max = Math.max(max, fst+snd);
		return fst;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 정점의 범위에 비해 간선의 갯수가 적으므로, 우선순위 큐를 이용해 다익스트라를 실행한다

1. i지점에서 다익스트라 실행 : i -> x의 최솟값을 구한다

  - x지점에서 다익스트라 실행 : x -> i의 최솟값을 구한다

2. 모든 i에 대해 1번의 결과를 실행 후, 그 최댓값을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int x = pint(st.nextToken());
		
		ArrayList<ArrayList<int[]>>graph=new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			graph.get(pint(st.nextToken())).add(new int[] {pint(st.nextToken()),pint(st.nextToken())});
		}
		
		PriorityQueue<int[]>pQ = new PriorityQueue<>(
				new Comparator<int[]>() {
					@Override
					public int compare(int[] o1, int[] o2) {
						return o1[1]-o2[1];
					}
				}
		);
		
		int max=0;
		
		//1. X지점에서 다익스트라(돌아오는 길)
		int[]costX = new int[n+1];//X로부터 다른 지점까지 cost
		Arrays.fill(costX, Integer.MAX_VALUE);
		costX[x]=0;
		for (int i = 1; i <= n; i++) {
			pQ.add(new int[] {i, Integer.MAX_VALUE});
		}
		pQ.add(new int[] {x,0});
		
		while(!pQ.isEmpty()) {
			int[]cur = pQ.poll();
			if(costX[cur[0]] < cur[1])continue;
			
			for (int i = 0; i < graph.get(cur[0]).size(); i++) {
				int[]next = graph.get(cur[0]).get(i);
				//더 짧으면 갱신
				if(costX[cur[0]] + next[1]< costX[next[0]]) {
					costX[next[0]]=costX[cur[0]] + next[1];
					pQ.add(new int[] {next[0], costX[next[0]]});
				}
			}
		}

		//2. 그 외 지점에서 다익스트라(가는 길)
		for (int i = 1; i <= n; i++) {
			if(i==x)continue;
			
			int[]costI = new int[n+1];//X로부터 다른 지점까지 cost
			Arrays.fill(costI, Integer.MAX_VALUE);
			costI[i]=0;
			for (int j = 1; j <= n; j++) {
				pQ.add(new int[] {j, Integer.MAX_VALUE});
			}
			pQ.add(new int[] {i,0});
			
			while(!pQ.isEmpty()) {
				int[]cur = pQ.poll();
				if(costI[cur[0]] < cur[1])continue;
				
				for (int j = 0; j < graph.get(cur[0]).size(); j++) {
					int[]next = graph.get(cur[0]).get(j);
					//더 짧으면 갱신
					if(costI[cur[0]] + next[1]< costI[next[0]]) {
						costI[next[0]]=costI[cur[0]] + next[1];
						pQ.add(new int[] {next[0], costI[next[0]]});
					}
				}
			}
			
			max = Math.max(max, costI[x]+costX[i]);
			
		}
		System.out.println(max);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 트리의 차수가 2 이상 커지지 않는다는 글이 있지만, 2 이상의 자식도 가정하고 작성

  - 관련글 (링크)

1. A노드가 root인 트리의 지름은?

  - 자식 노드 B,C,D가 있을 때, 각 자식 트리의 최대 깊이들 중 1, 2순위의 합이다

2. 자식 서브트리의 최대 깊이는? 재귀를 통해 최대 깊이만 반환토록 해 구한다

  - 자식이 없으면 0을 반환

  - 자식의 최대 깊이 + root로부터의 cost = 최대 깊이

3. 자식들을 순회하며 길이를 구하고, 1위와 2위를 구한 후 1+2의 결과로 지름을 갱신

  - 1순위만을 반환해 부모 트리의 연산에 이용한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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());
		graph = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = pint(st.nextToken());
			int m = pint(st.nextToken());
			int c = pint(st.nextToken());
			
			graph.get(n).add(new int[] {m,c});
		}
		
		rec(1);
		System.out.println(max);
	}
	static int max=0;
	static ArrayList<ArrayList<int[]>>graph;
	
	static int rec(int node) {
		int fstMin=0, sndMin=0;
		
		for (int i = 0; i < graph.get(node).size(); i++) {
			int[] cur = graph.get(node).get(i);
			
			int temp = cur[1] + rec(cur[0]);
			
			if(fstMin<temp) {
				sndMin=fstMin;
				fstMin=temp;
			}
			else if(sndMin<temp) {
				sndMin=temp;
			}
		}
		max=Math.max(max, fstMin+sndMin);
		return fstMin;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. postorder는 좌측 서브트리 - 우측 서브트리 - root이므로, 그 마지막 원소가 root이다

  - inorder는 좌측 - root - 우측 이므로, 위에서 구한 root 값을 찾음으로서 좌측/우측 서브트리의 크기를 구할 수 있다.

1. inorder의 시작과 끝, postorder의 시작과 끝 총 4개의 인덱스를 관리한다

2. root를 찾은 후 root - 좌 - 우 순서를 맞추기 위해

  - root를 출력문에 넣고

  - in/post의 시작점부터 좌측 서브트리의 길이만큼 인덱스를 구성해 재귀

  - in/post의 끝점부터 우측 서브트리의 길이만큼 인덱스를 구성해 재귀

3. 서브트리의 인자가 없으면 반환, 1개면 출력문에 삽입 후 반환한다

* 시간 향상을 위해, inorder의 index를 미리 생성해 사용할 수 있다

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));
		sb = new StringBuilder();
		
		int N = pint(br.readLine());
		inorder = new int[N];
		inorderIdx = new int[N+1];
		postorder = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++) {
			inorder[i]=pint(st.nextToken());
			inorderIdx[inorder[i]]=i;
		}
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < N; i++)postorder[i]=pint(st.nextToken());
		
		pre(0,N-1,0,N-1);
		
		System.out.println(sb);
	}
	static StringBuilder sb;
	static int[]inorder;
	static int[]inorderIdx;
	static int[]postorder;
	
	static void pre(int inS, int inE, int postS, int postE) {
		if(inS>inE)return;
		if(inE==inS) {
			sb.append(inorder[inS]).append(" ");
			return;
		}
		//post의 마지막 = 현재 서브트리의 root
		int root = postorder[postE];
		
		//root를 inorder에서 찾는다
		int cnt=inorderIdx[root];
		
		//root삽입
		sb.append(root).append(" ");
		//왼쪽
		pre(inS, cnt-1, postS, postS+(cnt-inS)-1);
		//오른쪽
		pre(cnt+1, inE, postS+(cnt-inS), postE-1);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 인구의 수는 항상 양수이므로, 모든 구역이 한쪽 선거구에 속할 경우는 고려하지 않아도 된다

  - N:0의 인구의 차이는, N-1:1의 인구의 차이보다 항상 클 테니까

1. 모든 선거구의 부분집합 S을 구한다(sub함수)

2. S에 속한 한 선거구, S에 속하지 못한 한 선거구를 선택해, 각각 bfs를 실행한다

  - bfs를 돌며 선거구의 개수와 그 인구수를 누적한다

3. 두 bfs의 결과 선거구의 합이 전체 선거구의 합과 같다면, 잘 연결된 두개의 선거구가 존재한다는 것

  - 누적한 인구의 차이를 반환한다

4. 3 결과값의 최종 최솟값을 출력한다

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

public class Main{
	
	static int N, min;
	static int[]people;
	static boolean[][]adj;
	static Queue<Integer>pick = new LinkedList<Integer>();
	static Queue<Integer>nonpick = new LinkedList<Integer>();
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		min=Integer.MAX_VALUE;
		people=new int[N];
		adj=new boolean[N][N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) people[i] = pint(st.nextToken());
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			st.nextToken();
			while(st.hasMoreTokens()) adj[i][pint(st.nextToken())-1]=true;
		}
		
		sub(0, 0);
		System.out.println(min==Integer.MAX_VALUE? -1 : min);
		
	}
	
	static void sub(int cnt, int mask) {
		if(cnt==N) {
			//mask : 선택한 노드
			min=Math.min(bfs(mask), min);
			return;
		}
		sub(cnt+1, mask|1<<cnt);
		sub(cnt+1, mask);
	}
	
	static int bfs(int mask) {
		//bfs두번 실행, 모든 노드를 탐색하는가?
		int s1=-1, s2=-1;
		for (int i = 0; i < N; i++) {
			if((mask&1<<i)!=0)s1=i; // 1인 노드 중 아무거나
			else s2=i; // 0인 노드 중 아무거나
		}
		
		int cnt1=0, total1=0, temp=mask;
		if(s1!=-1) {
			pick.offer(s1);
			temp^=1<<s1; // 방문 노드 삭제
			total1+=people[s1];
			cnt1++;
		}
		while(!pick.isEmpty()) {
			int cur = pick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)!=0 && adj[cur][i]) {
					pick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total1+=people[i];
					cnt1++;
				}
			}
		}
		
		int cnt2=0, total2=0; temp=mask;
		if(s2!=-1) {
			nonpick.offer(s2);
			temp^=1<<s2; // 방문 노드 삭제
			total2+=people[s2];
			cnt2++;
		}
		while(!nonpick.isEmpty()) {
			int cur = nonpick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)==0 && adj[cur][i]) {
					nonpick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total2+=people[i];
					cnt2++;
				}
			}
		}
		if(cnt1+cnt2==N)return Math.abs(total1-total2);
		else return Integer.MAX_VALUE;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}