선장 일지

• 생각

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

• 코드

정답 코드 : 에라토스테네스의 체를 이용해 소수가 아닌 수 들을 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;

	}
}

• 생각

1. 이런 문제들은 대부분 규칙이 있다. 

위의 사진으로 보면 이해가 잘 될 것이다. 5의 배수마다 0의 count 값이 증가하는 것을 볼 수 있다. 

근데 중요한 점은 입력값이 25일 때 1씩 증가하던 count 값이 2가 증가한다.

이유는 뒷자리가 0이 n개 있다는 의미는 2와 5개 n개씩 짝지어 존재한다는 것이다.

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스럽게 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

즉, 기본적으로 5의 개수에 따라 값이 변화한다고 볼 수 있다. 

• 코드

정답 코드 : 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 구해주면 된다.

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

public class Algorithm {
	static int N;

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

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

	private static int CountZero() {
		int count = 0;
		while (N >= 5) {
			count += N / 5;
			N /= 5;
		}

		return count;
	}
}