easy blog

DFS로 시도했으나 오답이다 이유를 생각해보면, DFS는 한붓그리기 라고 생각하면 된다.

파이프를 최단거리로 지나가는 경우도 생각할 수 있지만, 빙 돌아가는 경우에는 Level에 대한 부분이 애매해져버린다.

다른 풀이를 보니 visited 배열을 잘 사용해서 풀이 하는 경우가 있는것 같으나  visited를 구성하는 것이 번거로워 bfs로 변경함 ( 문제를 많이 풀다 보면, 둘을 번갈아가며 구현하는데 큰 어렴은 없다.)

단순하게 풀이하려 노력했다.

각 파이프 모양에서 나올 수 있는 움직임을 2차원 배열인 dx,dy로 저장.

보통의 bfs에서는 다음 단계(nr,nc)로 이동하고 보통 끝나지만 파이프가 연결됐는지 확인하기 위해

이동한 좌표(nrnr,ncnc) 에서 원래의 파이프(nr,nc)로 돌아올 수 있는지 확인을 하고 Q에 넣어주면 된다.

다른 사람들은 타입별로 파이프를 매핑해서 풀었는데, 이 방법이 더 직관적이지 않나 하는 생각이 든다.

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


class Solution {

	static int N, M, R, C, L;
	static int[][] dx = { {}, { 1, -1, 0, 0 }, { 1, -1 }, { 0, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
	static int[][] dy = { {}, { 0, 0, -1, 1 }, { 0, 0 }, { 1, -1 }, { 1, 0 }, { 1, 0 }, { 0, -1 }, { 0, -1 } };
	static int[][] map;
	static boolean[][] visited;
	static int answer;
	private static boolean DBG = false;

	public static void main(String args[]) throws Exception {


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			answer = 0;
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			R = Integer.parseInt(st.nextToken());
			C = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			//dfs(0, R, C);
			bfs();
			
			sb.append(String.format("#%d %d\n",test_case, answer));
			//System.out.println(answer);
		}
		
		System.out.println(sb);
	}

	private static void bfs() {
		Queue<int []> Q = new LinkedList<>();
		
		Q.offer(new int[]{R,C});
		
		int level = 0 ; 
		while(!Q.isEmpty()) {
			
			if( level ==L) {
				return;
			}
			
			
			int size = Q.size();
			for ( int t = 0 ; t < size ; t++) {
				int[] pos =Q.poll();
				int r= pos[0], c=pos[1];
				if (visited[r][c])
					continue;
				
				visited[r][c] = true;
				answer++;
				
				int now = map[r][c];
				for (int i = 0; i < dx[now].length; i++) {
					
					int nr = r + dx[now][i];
					int nc = c + dy[now][i];
										
					if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
						int next = map[nr][nc];
						if(DBG)
						System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
						for (int j = 0; j < dx[next].length; j++) {						
							int nrnr = nr + dx[next][j];
							int ncnc = nc + dy[next][j];						
							if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
									nrnr == r && ncnc == c) {
								if(DBG)
								System.out.printf("offer[%d %d]next : %d\n", nr,nc,next);
								Q.offer(new int[] {nr,nc});
							}

						}

					}
				}
				
				
			}
			
			level ++;
			if(DBG)
			System.out.println("level : "+level);
			
		}
		
		
	}

	private static void dfs(int level, int r, int c) {

		if (visited[r][c])
			return;
		
		visited[r][c] = true;
		if(DBG)
		System.out.printf("visited [%d %d] set true\n", r,c, visited[r][c]);
		answer++;
		if(DBG)
		System.out.printf("enter & count [%d %d] %d\n", r,c ,answer);

		if (level == L+1) {
			return;
		} else {
			int now = map[r][c];
			for (int i = 0; i < dx[now].length; i++) {
				
				int nr = r + dx[now][i];
				int nc = c + dy[now][i];
				
				
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc]!=0&& !visited[nr][nc]) {
					int next = map[nr][nc];
					if(DBG)
					System.out.printf("from[%d %d]to[%d %d]next map : %d visited : %b\n",r,c, nr,nc,next,visited[nr][nc] );
					for (int j = 0; j < dx[next].length; j++) {						
						int nrnr = nr + dx[next][j];
						int ncnc = nc + dy[next][j];						
						if (nrnr >= 0 && nrnr < N && ncnc >= 0 && ncnc < M && 
								nrnr == r && ncnc == c) {
							if(DBG)
							System.out.printf("dfs[%d %d]next : %d\n", nr,nc,next);
							dfs(level + 1, nr, nc);
						}

					}

				}
			}

		}

	}
}

순열 사이클 : https://www.acmicpc.net/problem/10451

인접행렬을 순회하며 자기 자신을 마주치기 전까지 돌면 된다.

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

public class Main {

	static int N, T;
	static int answer = 0;
	static ArrayList<Integer>[] adj;
	static boolean[] visited;
	private static boolean DBG = false;

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

		T = Integer.parseInt(br.readLine());
		for (int test_case = 0; test_case < T; test_case++) {
			N = Integer.parseInt(br.readLine());
			visited = new boolean[N + 1];
			adj = new ArrayList[N + 1];
			for (int i = 1; i <= N; i++) {
				adj[i] = new ArrayList<Integer>();
			}
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				adj[i].add(Integer.parseInt(st.nextToken()));
			}

			for (int i = 1; i <= N; i++) {
				if (!visited[i])
					check(0, i, adj[i].get(0));
			}

			System.out.println(answer);
			answer =0;
		}
	}

	private static void check(int index, int s, int v) {

		if (v == s) {
			answer++;
			return;
		}

		if (visited[v])
			return;
		visited[v] = true;

		check(index + 1, s, adj[v].get(0));

	}

}

이분 그래프 : https://www.acmicpc.net/problem/1707

https://toastfactory.tistory.com/115

https://kukekyakya.tistory.com/96

DFS 및 BFS풀이

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

import java.util.*;

public class Main {

	static int V, E, T;
	static boolean DBG = false;
	static String answer = "YES";
	static ArrayList<ArrayList<Integer>> graph;
	static int[] visited, team;
	static int RED = -1;
	static int GREEN = 1;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			answer = "YES";
			found = false;
			StringTokenizer st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			visited = new int[V];
			team = new int[V];
			graph = new ArrayList<ArrayList<Integer>>();

			for (int i = 0; i < V; i++) {
				graph.add(new ArrayList<Integer>());
			}

			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int v1 = Integer.parseInt(st.nextToken()) - 1;
				int v2 = Integer.parseInt(st.nextToken()) - 1;
				graph.get(v1).add(v2);
				graph.get(v2).add(v1);
			}

			if (DBG) {
				int i = 0;
				for (ArrayList<Integer> arr : graph) {
					System.out.print("i : [" + i + "] ");
					i++;
					for (int v : arr) {
						System.out.print(v + " ");
					}
					System.out.println();
				}

			}

			for (int i = 0; i < V; i++) {
				if (visited[i] == 0) {
					dfs(0, i, 1);
					if (found)
						break;
				}
			}

			/*
			 * for (int i = 0; i < V; i++) if (team[i] == 0) { if (!bfs(i)) break; }
			 */

			System.out.println(answer);
		}

	}

	static boolean found = false;

	private static void dfs(int level, int vex, int color) {

		if (visited[vex] != 0)
			return;
		visited[vex]=1;
		team[vex] = color;

		for (int v : graph.get(vex)) {
			if (team[v] == team[vex]) {
				answer ="NO";
				found =true;
				return;
			}
			dfs(level + 1, v, color * -1);
		}

	}

	private static boolean bfs(int vex) {
		Queue<Integer> Q = new LinkedList<>();

		Q.offer(vex);
		team[vex] = RED;

		while (!Q.isEmpty()) {
			int now = Q.poll();
			for (int n : graph.get(now)) {
				if (team[now] == team[n]) {
					answer = "NO";
					return false;
				}
				if (team[n] == 0) {
					team[n] = team[now] * -1;
					Q.add(n);
				}

			}
		}
		return true;
	}

}

롤러코스터  : https://www.acmicpc.net/problem/2873

참조 사이트 :  https://dundung.tistory.com/45

확인용 input

4 3
5 1 3
2 4 8
1 1 2 
1 1 1

3 4
5 1 3 1
2 4 8 1
1 1 2 1

4 4
10 10 10 10
1  10 10 10
10 10 10 10
10 10 10 10

참조 사이트에서 흰색칸을 피해가는 경우, 그 칸을 포함 총 3개를 놓치게 된다. 

따라서 4by 4의 경우 아래와 같이 나왔다.

S 1 3 1

1 3 1 3

3 1 3 1

1 3 1 E

어떻게 풀까 고민을 했지만 떠오르는 것이 없었다.

사이트를 확인해보니, 흑/백 체스판을 구별을 하고, 3인 부분은 무시하고 1로 구성된 부분에서 최소값을 찾아 그 부분만 지나지 않도록 구현을 하더라 (이 부분에서 탐욕법이 적용되었다고 생각한다.)

X 10 X 10

10 X 10 X

X 10 X 10

1 X 10 X

이런 식으로 두고 최소값을 찾아 주는데, 루프에서 (i+j)%2==0인 부분만 확인하면된다.

나머지 풀이법은 사이트 참조.

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

import java.util.*;

public class Main {

	static int R, C;
	static boolean DBG = false;
	static int[][] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new int[R][C];

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		StringBuilder sb = new StringBuilder();
		StringBuilder sb2 = new StringBuilder();

		if (R % 2 == 1) {
			for (int i = 0; i < R; i++) {
				if (i % 2 == 0) {
					for (int j = 0; j < C-1; j++) {
						sb.append('R');
					}
					if ( i != R-1)
						sb.append('D');						
				} else {
					for (int j = C - 2; j >= 0; j--) {						
						sb.append('L');
					}
					sb.append('D');	
				}

			}
		} else if (C % 2 == 1) {
			for (int i = 0; i < C; i++) {
				if (i % 2 == 0) {
					for (int j = 0; j < R-1; j++) {
						sb.append("D");
					}
					if ( i != C-1)
						sb.append("R");
					
				} else {
					for (int j = R - 2; j >= 0; j--) {
						sb.append( "U");
					}
					sb.append("R");
				}
			}

		} else {// 둘다 짝수
			int min = Integer.MAX_VALUE;
			int mc = 0, mr = 0;
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if ((i + j) % 2 == 1) {
						if (arr[i][j] < min) {
							min = arr[i][j];
							mr = i;
							mc = j;
						}
					}
				}
			}
			int sr = 0;
			int sc = 0;
			int er = R - 1;
			int ec = C - 1;

			while (er - sr > 1) {

				if (sr / 2 < mr / 2) {
					int tmp = C - 1;
					while (tmp-- > 0)
						sb.append('R');
					sb.append('D');
					tmp = C - 1;
					while (tmp-- > 0)
						sb.append('L');
					sb.append('D');
					sr += 2;
				}

				if (mr / 2 < er / 2) {
					int tmp = C - 1;
					while (tmp-- > 0)
						sb2.append('R');
					tmp = C - 1;
					
					sb2.append('D');
					while (tmp-- > 0)
						sb2.append('L');
					sb2.append('D');
					er -= 2;
				}
			}

			while (ec - sc > 1) {
				if (sc / 2 < mc / 2) {
					sb.append('D');
					sb.append('R');
					sb.append('U');
					sb.append('R');
					sc += 2;
				}
				if (mc / 2 < ec / 2) {
					sb2.append('D');
					sb2.append('R');
					sb2.append('U');
					sb2.append('R');
					ec -= 2;
				}
			}
			if (sr == mr) {
				sb.append('D');
				sb.append('R');
			} else {
				sb.append('R');
				sb.append('D');
			}
			sb.append(sb2.reverse());
		}
		System.out.println(sb);
	}

}

회의실 배정 : https://www.acmicpc.net/problem/1931

1. 먼저 끝나는 회의 부터 선택한다.

2. 끝나는 시간이 같은 경우, 늦게 시작하는 회의를 선택한다.

2번을 고려하지 않는다면 아래의 반례에서 오답을 출력하게 된다.

반례 : 

2
1 1
0 1

2

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

import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static int[][] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, (t1, t2) -> {
			if ( t1[1] == t2[1])
				return t1[0]-t2[0];
			return t1[1] - t2[1];
		});

		if (DBG) {
			for (int i = 0; i < N; i++) {
				System.out.printf("[%d %d]\n", arr[i][0], arr[i][1]);
			}
		}

		int cnt = 0;
		int endTime = 0;
		for (int i = 0; i < N; i++) {
			if (endTime <= arr[i][0]) {
				cnt++;
				endTime = arr[i][1];
			}
		}
		System.out.println(cnt);

	}

}

병든 나이트 : https://www.acmicpc.net/problem/1783

제약 조건: 

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 
병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 
이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

조건을 쓴 사람의 설명이 부족한건지 이해하지 못한 내가 멍청한 건지..

이동 방법에 제약이 없다는 말의 의미를 해석할 때, 머리가 터질것 같았다.

처음엔 이동방법에 제약이 없다는 말을 4방향 +1칸씩 이동가능하며 이를 횟수로 4번 가능하다 라고 해석해서 실패했다.

아무리 예시에 대입해도 답이 나오지 않음.

참조 : https://data-make.tistory.com/653

위의 사이트를 참조하고 나서 겨우 의미가 이해가 되었고 문제가 해결됐다.

말의 움직임은 문제에 주어진 대로만 가능하며 이동방법에 제약이 없다는 것은 제시된 움직 중 각각의 동작을 4번까지 할 수 있다는 것이다.

이 조건을 이해하면 그림만 그려보면 답이 나온다.

#N=1

말이 행동할 수 있는 경우 없음. 

#N=2

2칸 증가할 때마다 행동이 하나씩 늘어남. 

1,1

2,1

3,2

4,2

5,3,

6,3

7,4

8,4

9,4

4회 이동까지만 허용되므로 m이 홀수인 경우 몫이 반올림 되지 않으므로 +1을 해준 뒤 몫을 취한다. 

answer = min ( 4, (m+1)/2) 가 된다.

#N=3

M 1한칸당 1개씩 늘어난다. 

M < 7 인 경우, N=2와 같은 이유로 4개가 최대가 되며 M=7을 기점으로 M 한칸당 1개씩 증가한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int answer = 1;
		if( N == 1)
			answer = 1;
		else if (N == 2)
			answer = Math.min(4, (M+1)/2);
		else if (M  < 7 ) {
			answer = Math.min(4, M);
		} else {
			answer = 5 + (M-7);
		}
		
		System.out.println(answer);

	}

}

30 : https://www.acmicpc.net/problem/10610

그리디 문제...

순열과 이것 저것 시도해보다 자리수가 10^5인 것을 보고 String으로 선회했다.

배수판정법 위키를 찾아보니.. 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

30의 배수 판정법은 두가지 조건을 만족한다.

1. 각자리수의 합이 3의 배수일 것

2. 0으로 끝날 것

위 조건만 알면 코딩은 별게 없다.

0을 뒤로 빼거나 다른 걸 생각할 필요없이 내림차순 정렬한 값이 최대값이 된다.

그리디란... 참 알면 별거 아닌것 같고, 코드는 효율적인데 처음 봤을 땐 직관적이지 않아서 나랑은 잘 안맞는 것 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N;
	static boolean DBG = false;
	static boolean[] visited;
	static Integer[] arr;
	static String answer = "-1";

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String s = st.nextToken();		
		arr = new Integer[s.length()];
		
		int sum =0;
		int idx= s.length()-1;
		for (char c : s.toCharArray()) {
			arr[idx] = c-'0' ;
			sum += arr[idx];
			idx--;
		}
		
		if ( sum % 3 ==0 && s.lastIndexOf('0') !=-1 ) {
			Arrays.sort(arr, Collections.reverseOrder());
			StringBuilder sb =new StringBuilder();
			for ( int v : arr)
				sb.append(v);
			
			answer = sb.toString();
		} else {
			System.out.println(answer);			
		}
	
	}

}

대회 or 인턴 : https://www.acmicpc.net/problem/2875

숏코드 : https://geehye.github.io/baekjoon-2875/#

#Case1  

첫 접근으로 문제에 조건에 따라 식을 만들어준다.

N - 2*max + M - max >= K

이를 정리해주면, 

N + M - 3*max >= K 

그런데, 남녀가 쌍을 이뤄야 하므로 N 및 M에 개별 조건이 생기게 된다.

N - 2*max >=0 && M - max >=0 

위 조건들을 만족하는 i를 출력 해주면 답이된다.

#Case2

N + M - 3*max >= K 까지 동일하게 구한다.

여기서 N/2 > M 이면 여학생의 수가 남게 되므로 여학생을 기준으로 max를 계산

반대로 N/2 < M 이면 남학생의 수가 부족하게 되므로 남학생을 기준으로 max를 계산해야 한다.

그렇지 않으면 팀을 구성하는 성비가 맞지 않게 된다.

따라서 max = N/2 < M ? N/2 : M

성비에 맞게 max를 구했으니 첫번째 조건을 만족하는지 확인해야한다.

계산한 max값을 이용해 팀을 구성하고 남는 학생을 K에서 빼주면, 인턴에 필요한 학생이 몇명 더 필요한지 나온다.

남는 학생이 더 많으면 K는 음수가 된다.

K -= N + M - 3*max

만약 학생이 더 필요하다면 팀을 하나 해체(3명) 해야하므로 루프를 돌 때마다 K에서 3을 빼준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int N, M, K;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int answer = 0;
		
		//Case 1
		for (int i = 0; K <= (N + M - i * 3 ) && N - i*2 >= 0 && M - i >= 0; i++) {
			answer = Math.max(answer, i);
		}
		
		//Case 2
		int max = N/2 < M ? N/2: M;
		
		K -= N+M-3*max;
		
		while ( K > 0 ) {
			K -= 3;
			max--;
		}
		
		
		System.out.println(max);

	}
}

민호와 강호 : https://www.acmicpc.net/problem/11662

참조 사이트 :

1. https://conpulake.tistory.com/29

2. https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=221432986308&proxyReferer=https:%2F%2Fwww.google.com%2F 

삼분 탐색이란 개념을 처음 알게되었다.

범위를 lo, hi 구간으로 잡고 p, q 라는 구간을 설정한다.

p는 1/3지점 , q는 2/3지점을 나타낸다.

p = (hi - lo) / 3 + lo = (hi + 2lo)/3 

q = 2*(hi - lo) / 3 + lo = (2hi + lo)/3

삼분 검색의 경우, 아래로 볼록 하거나 위로 볼록한 형태의 구간에서 사용 가능하다고 한다. 

정확하게는 더 공부를 해봐야겠으나, 일반적인 2차 함수의 구간을 나타내는 범위에 사용 가능할 것으로 보인다.

우선, 문제를 이해하기 위해 시간에 따른 민호와 강호 사이의 거리를 구하는 식은 아래와 같다.

문제를 처음에 해석하는데 살짝 애를 먹긴했는데.. 다음과 같이 구할 수 있다.

A 점에서 B점으로 이동하는데 걸리는 시간을 1초라고 생각하고,  시간의 resolution을 10^6으로 생각하면, AB 사이의 거리는 속도가 된다.

속도 * 10^-6*t (0<= t<=10^6)를 해주면 변위가 되므로 원래 위치에서 더해주면 t 시점의 위치가 된다.

민호의 위치 = A의 위치 + (B의 위치 - A의 위치)* 시간

강호의 위치 = C의 위치 + (D의 위치 - C의 위치)* 시간

이를 f()메소드에 구현하였으며, 시간을 삼분탐색할 값으로 선정하였다.

이해한 바에 따라 hi 및 lo 범위를 축소 시키면 일정 범위 이하로는 줄어들지 않아 무한루프에 빠지거나

정확도가 떨어지는 현상이 발생한다고 한다.

현 문제에서는 hi-lo 의 값이, 최소 단위인 1e-6보다 작아지는 경우, 루프를 빠져나오고,

구해진 hi-lo 를 순회하여 min 값을 구해 답을 찾았다.

hi 값이 변하면 답이 크게 틀어지는 것으로 보아, 범위 설정에 따라 값이 어떻게 변하는지 더 스터디가 필요할 것 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static double[] x, y;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		x = new double[4];
		y = new double[4];

		for (int i = 0; i < 4; i++) {
			x[i] = Double.parseDouble(st.nextToken());
			y[i] = Double.parseDouble(st.nextToken());
		}
		//10^6 == 1e6
		//10^-6 == 1e-6
		double lo = 0;
		double hi = 1e6;

		while (hi - lo >= 1e-6) {

			double p = (hi + 2 * lo) / 3;
			double q = (2 * hi + lo) / 3;

			if (f(p) >= f(q))
				lo = p;
			else
				hi = q;
			if (DBG)
				System.out.printf("lo: %f hi : %f\n", lo, hi);
		}

		double answer = Double.MAX_VALUE;
		for (int i = (int) lo; i <= hi; i++) {
			answer = Math.min(f(i), answer);
		}

		bw.write(String.format("%f\n", answer));
		br.close();
		bw.close();

	}

	private static double f(double time) {
		double nx1 = x[0] + (x[1] - x[0]) * time * 1e-6;
		double ny1 = y[0] + (y[1] - y[0]) * time * 1e-6;
		double nx2 = x[2] + (x[3] - x[2]) * time * 1e-6;
		double ny2 = y[2] + (y[3] - y[2]) * time * 1e-6;
		return getDistance(nx1, nx2, ny1, ny2);
	}

	private static double getDistance(double x1, double x2, double y1, double y2) {
		return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
	}

}

숫자카드 : https://www.acmicpc.net/problem/10815

입력이 1천만 정도로 int의 최고값에 미치지 못하므로 넉넉한 메모리를 활용하여

간단하게 풀이 가능함. 

시간 676ms 

메모리 : 153,368KB => boolean 배열을 활용하는데 20MB를 사용함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;	
	static boolean[] ar;
	static int MAX = 10000000;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());

		ar = new boolean[2 * MAX + 1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			ar[Integer.parseInt(st.nextToken()) + MAX] = true;
		}

		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			sb.append(ar[Integer.parseInt(st.nextToken()) + MAX] ? 1 : 0).append(' ');
		}

		System.out.println(sb);

	}

}

이문제가 이분탐색의 항목에 있는 이유를 몰라 검색을 해보니..

아래와 같은 방식으로 코드를 구현해 놓은게 있다.

https://dragon-h.tistory.com/30

이진 탐색을 통한 포함 유무 확인 방법 

시간: 1048ms

메모리 : 135,300KB

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());

		arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);
		
		M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			boolean res = binarySearch(arr, Integer.parseInt(st.nextToken()));
			bw.write(res ? "1 " : "0 ");
		}

		br.close();
		bw.close();

	}

	static boolean binarySearch(int[] list, int target) {
		int lt = 0;
		int rt = list.length - 1;
		boolean result = false;
		while (lt <= rt) {
			int mid = (rt + lt) / 2;
			if (list[mid] > target) {
				rt = mid - 1;
			} else if (list[mid] < target) {
				lt = mid + 1;
			} else {
				result = true;
				break;
			}

		}
		return result;
	}

}