선장 일지

• 생각

ATM의 모든 사람의 대기시간의 합을 구하는 문제이다.

앞에사람의 작업시간이 길어질 수록 총 대기시간이 길어지니 오름차순 정렬을 통해 대기시간을 최소로 해줘야한다.

• 코드

정답 코드 : arrays.sort를 통해 오름차순 정렬을 해준 뒤, 총 대기시간을 구해주었다.

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

public class Main {
	static int N;
	static int[] array;

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

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		array = new int[N];	
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());
		
		// 오름차순 정렬
		Arrays.sort(array);
	}
	
    private static int ReturnWaitingTime()
    {
    	int sum = 0;
				
		for(int i = 0; i < N; i++) {
			sum += array[i] * (N - i);
		}
    	
        return sum;
    }
}

• 생각

최대공약수를 구해주기만 하면 될듯

• 최대공약수구하는 방법 (재귀)

   private static int GCD(int x, int y)
    {
        if(x % y == 0) return y;
        return GCD(y, x%y);
    }

• 코드

정답 코드 : 단순 수학문제이다. 두 수의 최대공약수를 구해준 뒤 최대공약수로 A, B를 나누어주면 된다.

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

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();		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int B,C;
		for(int i = 0; i < N-1; i++) {
			B = Integer.parseInt(st.nextToken());
			C = GCD(A,B);
			sb.append(A/C + "/"+ B/C + "\n");
		}
	}
	
    private static int GCD(int x, int y)
    {
        if(x % y == 0) return y;
        return GCD(y, x%y);
    }
}

• 생각

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

}