선장 일지

• 생각

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

• 생각

 nCm이 뭐였는지 기억이 잘 나지않아서 풀어보게 되었다.  nCm => n! / (n-m)!m! 라고 보면 된다.

1. 재귀로 풀어질 것 같다.(long타입으로도 범위를 받아들일 수 없다고함. ==>> BIgInteger 사용 해야함) ==>> 시간 초과

• 코드

정답 코드 : 핵심은 long타입도 범위를 받아들일 수 없기 때문에 BigInteger을 사용하는 것이다. 

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

public class Main {
	static int N, M;

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

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

	private static BigInteger Combination() {
		BigInteger num1 = BigInteger.ONE;
		BigInteger num2 = BigInteger.ONE;
		for (int i = 0; i < M; i++) {
			num1 = num1.multiply(new BigInteger(String.valueOf(N - i)));
			num2 = num2.multiply(new BigInteger(String.valueOf(i + 1)));
		}

		return num1.divide(num2);
	}
}

• 생각

1. 입력으로 N이 주어지고, 출력으로 N자리 3의 배수의 개수를 출력해주면 되는 간단한 문제 첫번째 자리엔 0이 올 수 없고 0, 1, 2 차례대로 넣어주면 된다.

• 코드

정답 코드 : 입력으로 N이 주어지고, 출력으로 N자리 3의 배수의 개수를 출력해주면 되는 간단한 문제 첫번째 자리엔 0이 올 수 없고 0, 1, 2 차례대로 넣어주었다.

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

public class Main {
	static int N, count;

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

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

    private static void Calculate(int n, int sum){
        for(int i = 0; i < 3; i++){
            if(n == 0 && i == 0){
                continue;
            }
            if(n == N){
                if(sum % 3 == 0) count++;
                return;
            } else {
                Calculate(n + 1, sum + i);
            }
        }
    }
}