선장 일지

• 생각

-2진법 문제는 그냥 2진법으로 바꾸는 것처럼 풀면 될 것 같다. 단, 나누기와 나머지 연산할 때 -2를 해줘야한다는 것, 또한 나머지 연산할 때는 몫을 버리는 것이 아닌 올림을 해줘야한다.

새로운 방법(클릭하면 링크)

- Math.ceil()

• 코드

정답 코드 : 나머지를 list에 넣어둔 뒤 뒤에서부터 StringBuilder에 append시켜준다.

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

public class Main {
	static int N;
	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());
		sb = new StringBuilder();
		ArrayList<Integer> list = new ArrayList<>();
        
        if(N==0) { 
            System.out.println(N);
            System.exit(0);
        }
    
        while(N!=0) {
            list.add(Math.abs(N%-2));
            N=(int)Math.ceil((double)N/-2);
        }
        
        for(int i=list.size()-1; i>=0; i--)		// 반복문에서 한번씩 출력해주는 방법보다 빠름
            sb.append(list.get(i));
	}
}

• 생각

해당 숫자가 몇번째의 소수인지 찾으면 되는 문제이다. 소수를 찾는 것은 에라스토테네스의 체를 이용해 찾으면 될 것 같고, 에라스토테네스의 체 내에서 소수가 발견되면 몇번째 소수인지 체크하면서 반복문을 돌면 될 것 같다.

• 코드

정답 코드 : 에라스토테네스의 체를 이용해서 구해주는데, 위의 K 범위만큼 배열을 만들어서 사용하면 100점이 뜨지않는다. 이유는 500000를 입력하면 500000번째 소수를 구하는 것이기 때문에 범위를 더 크게 주어야한다. 점점 늘리면서 채점해봤는데 10000001정도에 100점이 뜬다.

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

public class Main {
	static int K;
	static int[] prime;

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

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		prime = new int[10000001];
		boolean[] check = new boolean[10000001];
		int index = 0;

		// 에라스토테네스의 체
		for (int i = 2; i <= 10000000; ++i) {
			if (!check[i]) {
				prime[index++] = i;
				for (int j = i + i; j <= 10000000; j += i) {
					check[j] = true;
				}
			}
		}
	}
}

• 생각

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다.

L일 동안 캠핑하고, P-L일 동안 안하고, 이 두 가지 상태가 반복 됌.

• 코드

정답 코드 : V/P (연속일), 연속일 * 연속 최대사용일수(L) => 사용가능 일 수 + 나머지일 수 더해줌. 

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

public class Main {
	static int L, P, V, count;
	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));
		StringTokenizer st = null;
		sb = new StringBuilder();
		count = 1;

		while (true) {
			st = new StringTokenizer(br.readLine());
			L = Integer.parseInt(st.nextToken());
			P = Integer.parseInt(st.nextToken());
			V = Integer.parseInt(st.nextToken());
			
			if (L == 0)			break;
			// V/P = 연속
			sb.append("Case " + count + ": " + ((V / P) * L + Math.min(L, V % P)) + "\n");
			count++;
		}
	}
}

• 생각

단순 수학문제 배열을 만들어서 해당하는 숫자 1을 1번 2를 2번 ..... 1000번까지 한 뒤, A부터 B까지 더한 값을 출력

• 코드

정답 코드 : 배열을 만들어 A~B 인덱스까지 더해준 숫자를 출력하였다.

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

public class Main {
	static int A, B, answer;
	static int[] array;

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

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		answer = 0;
		
		int index = 0;
		array = new int[1001];
		for(int i = 1; i < 1001; i++) {
			for(int j = 0; j < i; j++) {
				array[index++] = i;
				if(index > 1000) break;
			}
			if(index > 1000) break;
		}
	}
	
    public static void getSum() {
		for (int i = A - 1; i <= B - 1; i++) {
			answer += array[i];
		}
    }
}

• 생각 

1. stick의 초기 길이(64)에서 반씩 나누어주면서, 길이 X보다 더 작은 값이 나오면
   X 값을 해당 숫자만큼 차감시키고, 차감 횟수를 센다.
2. X 값이 0이 나올때까지 진행한 뒤, 차감 횟수를 출력한다.

• 코드

정답 코드 : 위의 방법대로 짠 코드이다.

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

public class Main {
	static int X, stick, answer;

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

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        X = Integer.parseInt(br.readLine());
        stick = 64;
        answer = 0;
	}
	
    public static void getStick() {
		while (stick > 0) {
			if (stick <= X) {
				X -= stick;
				answer++;
			}
			if (X == 0) {
				break;
			}
			stick /= 2;
		}
    }
}

• 생각

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

}