선장 일지

• 생각

T개 만큼의 숫자를 입력한 뒤 해당 수를 짝수 두개의 수로 나누어 떨어진 숫자 두개를 출력하면 된다. 단, 숫자의 차이는 최소여야 한다.

1. 에라토스테네스의 체를 통해 소수를 찾아 둔다.

2. 입력한수 / 2 한 값에서 부터 0까지 반복문을 돌면서 소수이고, 입력한수 - 반복문 도는 수를 했을 때 둘다 소수이면 출력한다.

• 코드

정답 코드 : 에라토스테네스의 체를 통해 소수를 찾고, 입력한수 / 2 값에서부터 반복문을 돌며 두개의 합이 입력한 수 이며 두 수 모두 소수이면서 값의 차이가 최소가 되는 값을 출력한다.

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

public class Main {
	static int N;
	static boolean[] check;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        N = Integer.parseInt(br.readLine());
		check = new boolean[10001];
        getPrimeNumber();
        sb = new StringBuilder();
        
        for(int t=0; t < N; t++) {
            int number = Integer.parseInt(br.readLine());
            
            for(int i = number/2; i > 0; i--) {
                int index1 = i;		// 소수 1
                int index2 = number - i;	// 소수 2
                if(!check[index1] && !check[index2]) {		// 둘 다 소수가 맞으
                    sb.append(index1 + " " + index2 + "\n");
                    break;
                }
            }
        }
	}
	
    public static void getPrimeNumber() {
		check[0] = check[1] = true;
		for (int i = 2; i <= 10000; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= 10000; j+=i) {
				check[j] = true;
			}
		}
    }

}

• 생각

저번 주에 풀었던 문제 중 소수찾기할 때 에라토스테네스의 체를 이용하여 찾았다. 이번 문제에서도 에라토스테네스의 체를 사용해서 풀어보면 좋을 것 같아서 풀어보았다.

• 코드

정답 코드 : 에라토스테네스의 체를 이용해 소수가 아닌 수 들을 true로 변경 해준다. 배열 중 false인 수들은 소수이다.

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

public class Main {
	static int N, count;
	static boolean[] check;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(count);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		check = new boolean[1001];
		count = 0;
		
		check[0] = check[1] = true;
		for (int i = 2; i <= 1000; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= 1000; j+=i) {
				check[j] = true;
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			if(!check[Integer.parseInt(st.nextToken())]) count++;
		}
	}

}

• 생각

두개의 분수를 입력하면 둘의 합을 출력하면 된다. 합친 분수의 분모는 분모끼리의 곱, 분자는 분자와 분모곱을 더 해주면 된다. 여기서 문제는 최대공약수를 빼줘야한다는 것이다.

1. 유클리드 호제법으로 최대공약수를 구한뒤 분자, 분모를 나누어서 출력해주면 된다.

• 코드

정답 코드 : 유클리드 호제법으로 최대공약수를 구해준 뒤, 합친 분수의 값에 나누어서 출력해줌.

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

public class Main {
	static int a, b, gcd;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println((a / gcd) + " " + (b / gcd));
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int a1 = Integer.parseInt(st.nextToken());
		int b1 = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int a2 = Integer.parseInt(st.nextToken());
		int b2 = Integer.parseInt(st.nextToken());

		a = a1 * b2 + a2 * b1;
		b = b1 * b2;
		
		gcd = getGCD(a, b);
	}

	public static int getGCD(int p, int q) {
		if (q == 0) {
			return p;
		}
		return getGCD(q, p % q);
	}

}

• 생각

N부터 M까지의 수 중 소수를 찾는 문제이다.

1. 에라토스테네스의 체를 통해 빠르게 소수를 찾는 방법이 있다. (잘 모르면 링크를 타고 들어가서 이해하길..)

2. 위의 방법으로 소수를 찾은 후 N부터 M까지 수 중에서 소수만 출력하면된다.

• 코드

정답 코드 : 에라토스테네스의 체를 통해 N과 M사이의 소수를 찾은 뒤 출력해줌

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

public class Main {
	static int N, M;
	static boolean[] check;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		FindDecimal();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		check = new boolean[M + 1];
		check[0] = check[1] = true;

	}

	private static void FindDecimal() {
		for (int i = 2; i <= M; i++) {
			if (check[i] == true) {
				continue;
			}
			// 해당 수로 나누어 떨어지는 수는 소수이므로 true로 check
			for (int j = i + i; j <= M; j+=i) {
				check[j] = true;
			}
		}
		for (int i = N; i <= M; i++) {
			if (check[i] == false)
				sb.append(i + "\n");
		}

	}
}

• 생각

1. 단순 수학 문제인 것 같다. 

• 코드

정답 코드 : 토너먼트는 한번 이루어질 때마다 사람이 반토막나고, 김지민과 임한수가 번호가 같아질 때 경기가 이루어 진다는 것을 고려해서 코딩했다.

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

public class Main {
    static int N, Kim, Lim;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(GoTournament());
	}

	private static void SetData() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Kim = Integer.parseInt(st.nextToken());
        Lim = Integer.parseInt(st.nextToken());
	}

	private static int GoTournament() {
		int count = 0;
		
		while(Kim != Lim) {
			Kim = Kim/2 + Kim%2;
			Lim = Lim/2 + Lim%2;
			count++;
		}
		
		return count;
	}
}

• 생각

1. 각각 인덱스 값의 차이를 배열에 저장한 뒤 오름차순 정렬해서 K개 만큼 뽑아내면 될까???

• 코드

정답 코드 : i, i+1의 차이의 값을 하나의 배열에 저장해 놓는다. 배열을 오름차순으로 정렬한 뒤 가장 작은 차이를 보이는 값을 N-K만큼 더 해주면 된다.

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

public class Main {
    static int N, K;
    static int[] array, temp;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMinValue());
	}

	private static void SetData() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        array = new int[N+1];
        temp = new int[N-1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	array[i] = Integer.parseInt(st.nextToken());        	
        }
        
        for (int i = 0; i < N - 1; i++)
            temp[i] = array[i + 1] - array[i];
        
        Arrays.sort(temp);
	}

	private static int FindMinValue() {
		int min = 0;		
	    for (int i = 0; i < N - K; i++) min += temp[i];
		
		return min;
	}
}

• 생각

1. 이전에 벽 부수고 이동하기 문제를 푼적이 있었다. 여기서 달라진 점은 벽이 1개냐 K개냐 라는 차이 하나만 있기때문에 벽을 체크해주는 부분을 1개가 아닌 K개로 바꾸면 잘 동작할 것 같았다.

• 코드

정답 코드 : bfs로 풀었다. 여기서 핵심은 중복제거를 check[N][M][K]로 벽을 지나오면서 왔는지 아닌지 중복체크를 해주는 방법을 사용해야지만 정확히 풀 수 있는 문제이다. 

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, M, minValue, K;
	static int[][] array;
	static boolean[][][] check;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		SetData();
		bfs();
        if(minValue == Integer.MAX_VALUE)
            System.out.println(-1);
        else    
            System.out.println(minValue);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		array = new int[N][M];
		check = new boolean[N][M][K+1];
		minValue = Integer.MAX_VALUE;
		String s;
		
		for (int i = 0; i < N; i++) {
			s = br.readLine();
			for (int j = 0; j < M; j++) {
				array[i][j] = s.charAt(j) - '0';
			}
		}
	}

	private static void bfs() {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { 0, 0, 1, 0 });

		while (!queue.isEmpty()) {
			int location[] = queue.poll();
			
			int count = location[2];
			int breakWall = location[3];
			if (location[0] == N - 1 && location[1] == M - 1) {
				minValue = Math.min(minValue, count);		// 마지막 위치에 도달했을 때 지나온 칸 수를 return
			}

			for (int direction = 0; direction < 4; direction++) {
				int r = location[0] + x[direction];
				int c = location[1] + y[direction];

				if (r < 0 || r >= N || c < 0 || c >= M)
					continue;
				if (array[r][c] == 1 && breakWall == K)	// 지나온 벽이 있고 다음 칸도 벽이면 진행 X
					continue;

				if (breakWall == K) {
					if (!check[r][c][breakWall] && array[r][c] == 0) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall});
					}
				} else { // 벽을 안부순 상태
					if (!check[r][c][breakWall] && array[r][c] == 1) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall + 1 });
					} else if (!check[r][c][breakWall] && array[r][c] == 0) {
						check[r][c][breakWall] = true;
						queue.offer(new int[] { r, c, count + 1, breakWall });
					}
				}
			}
		}
	}
}

• 생각

1. 내림차순으로 하나씩 체크하면서 뺴주려했는데 잘 안됌 - 정렬

2. 내림차순으로 하나씩 체크하면서 빼주려했는데 잘 됌 - arraylist

• 코드

정답 코드 : arraylist를 이용해 내림차순 정렬 후 하나씩 빼준다. box를 N개 빼면 날짜를 1일씩 증가시켜줌

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

public class Main {
	static int N, M;
	static ArrayList<Integer> crain, box;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMixValue());
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		crain = new ArrayList<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			crain.add(Integer.parseInt(st.nextToken()));

		M = Integer.parseInt(br.readLine());
		box = new ArrayList<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++)
			box.add(Integer.parseInt(st.nextToken()));

		Collections.sort(crain, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.compareTo(o1);
			}
		});
		Collections.sort(box, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.compareTo(o1);
			}
		});
	}

	private static int FindMixValue() {
		int count = 0;		// 걸린 시간
		
		// 가장 무거운 박스의 무게 > 크레인 최대 중량일 경우
		if (box.get(0) > crain.get(0))
			return -1;
		
		while (box.size() != 0) {
			int crainIndex = 0, boxIndex = 0;
			
			while (crainIndex < N) {
				if (boxIndex == box.size())
					break;
				// 현재 크레인 index 크기로 박스 index를 옮길 수 있으면
				if (box.get(boxIndex) <= crain.get(crainIndex)) {
					box.remove(boxIndex);
					crainIndex++;
				} else if (box.get(boxIndex) > crain.get(crainIndex)) {
					boxIndex++;
				}
			}
			count++;
		}
		return count;

	}
}