Coding Test/Step15. 약수, 배수와 소수 2 (9) 썸네일형 리스트형 [Java] 9단계. 창문 닫기 [13909번] https://www.acmicpc.net/problem/13909예제 입력13예제 출력11예제 입력224예제 출력24문제 접근N개의 창문과 N명의 사람 존재 N번째 사람은 N의 배수 창문을 열거나 닫음 처음엔 모든 창문이 닫혀있음 Ex) N = 3 1번째 사람은 1, 2, 3창문을 열음 (1, 1, 1) 2번째 사람은 2번 창문을 닫음 (1, 0, 1) 3번째 사람은 3번 창문을 닫음 (1, 0, 0) 따라서, 마지막에 열린 창문의 개수는 1개입력 첫째 줄 : 창문의 수와 사람의 수 N (1 출력 마지막에 열려 있는 창문 개수 출력문제 해결int의 범위는 21억 4748만 ~~ 이기 때문에 long을 굳이 쓰지 않아도 됨boolean[] window로 21억개의 에라토스테네스의 해를 사용하려 하였는데 .. [Java] 8단계. 골드바흐 파티션 [17103번] https://www.acmicpc.net/problem/17103예제 입력15681012100예제 출력111216문제 접근골드 바흐의 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있음 두 소수의 순서만 다른 것은 같은 파티션 입력 첫째 줄 : 테스트 케이스 개수 T (1 ~ T번째 줄 : 정수 N (2 Ex1) 6 = 3 + 3Ex2) 8 = 3 + 5Ex3) 10 = 3 + 7, 5 + 5Ex4) 12 = 5 + 7출력 각 테스트 케이스마다 골드바흐 파티션의 수 출력문제 해결에라토스테네스의 체로 소수를 미리 구해둠n - 첫번 째 소수 = 결과가 소수라면 (O)n - 두번 째 소수 = 결과가 소수가 아니라면 (X)...단, n / 2까지만 체크→ 그렇지 않으면, 10의 경우 3+7, 5+5,.. [Java] 7단계. 베르트랑 공준 [4948번] https://www.acmicpc.net/problem/4948예제 입력1110131001000100001000000예제 출력11432113510338392문제 접근입력 n → 적어도 하나 존재 (1 여러 개의 테스트 케이스 각 케이스는 n을 포함하는 한줄로 이루어짐 입력의 마지막에는 0이 주어짐출력 각 테스트 케이스에 대해서 n보다 크고, 2n보다 작거나 같은 소수의 개수 출력 문제 해결n ~ 2n 안에 포함되는 모든 소수를 출력하는 것은 n이 커졌을 때 너무 많은 비교가 필요에라토스테네스의 체를 사용하는 것이 효과적으로 보임1은 제외하고 2부터 시작하여 모든 숫자는 소수라고 가정int i = 2부터 시작하여 i의 배수는 모두 제거기존 풀이 [메모리 : 17,552 KB / 시간 : 160 ms]p.. [Java] 6단계. 소수 구하기 [1929번] https://www.acmicpc.net/problem/1929예제 입력13 16예제 출력13571113문제 접근입력 첫째 줄 : 자연수 M과 N이 주어짐 (1 출력 한 줄에 하나씩 오름차순으로 소수 출력문제 해결N ~ M까지 반복하여 소수 판별소수일 경우 true, 소수가 아닐 경우 false소수일 경우 StringBuilder에 추가기존 풀이 [메모리 : 19,368 KB / 시간 : 316 ms]public static void main(String[] args) throws IOException{ StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputStreamReader(Syste.. [Java] 5단계. 다음 소수 [4134번] https://www.acmicpc.net/problem/4134예제 입력13620100예제 출력1723101문제 접근입력 첫째 줄 : 테스트 케이스 개수 T ~ T번째 줄 : 정수 n (0 출력각각의 테스트 케이스에 대해 n이상의 가장 작은 소수를 한 줄씩 출력문제 해결정수 n은 최대 40억까지 입력이 가능하기 때문에 int의 범위를 벗어나 long을 사용해야 함소수인지 아닌지 판별하는 check 메서드의 조건0과 1은 소수가 아님2는 소수n % 2 == 0에서 짝수는 모두 걸러졌기 때문에 i = 3부터 시작하고 2씩 증가시킴→ 반복문의 횟수를 줄이기 위함 조건식은 루트n까지→ 반복문의 횟수를 줄이기 위함 ex) n = 121121 % 3 != 0121 % 5 != 0121 % 7 != 0121 % 9.. [Java] 4단계. 가로수 [2485번] https://www.acmicpc.net/problem/2485예제 입력1413713예제 출력13예제 입력24261218예제 출력25문제 접근입력 첫째 줄 : 이미 심어져이쓴 가로수의 수를 나타내는 하나의 정수 N (3 ~ N번째 줄 : 가로수의 위치가 양의 정수로 주어짐 ( 가로수 위치를 나타내는 정수는 모두 다름(중복 X) 오름차순으로 주어짐 출력 모든 가로수가 같은 간격이 되도록 새로 심어야하는 가로수의 최소수를 첫 번째 줄에 출력문제 해결각각의 가로수 간격의 최대 공약수를 구함(가장 큰 가로수 위치 - 가장 작은 가로수 위치) / 최대공약수 + 1 = 총 가로수의 개수총 가로수 개수 - N = 심어야하는 가로수 개수기존 풀이 [메모리 : 22,960 KB / 시간 : 232 ms]public s.. [Java] 3단계. 분수 합 [1735번] https://www.acmicpc.net/problem/1735예제 입력12 73 5예제 출력131 35문제 접근입력 첫째 줄, 둘째 줄 : 각 분수의 분자와 분모가 주어짐 '분자 분모' 네 자연수는 30,000이하출력 첫째 줄 : 구하고자하는 기약분수의 분자와 분모를 출력문제 해결분모의 최소공배수를 구함최소공배수 / 첫째 줄 분모 = A최소공배수 / 둘째 줄 분모 = B(첫째 줄 분자 * A) + (둘째 줄 분자 * B) = 분자최소공배수 = 분모값이 매우 커질 수 있기 때문에 long을 사용분수를 합치고 나서 분모와 분자가 최대공약수로 나누어야만 기약분수가 성립 됨2/4, 10/25 → 50/100 + 40/100 = 90/100 → 기약분수가 아님최대공약수 10 : 90 / 10, 100 / .. [Java] 2단계. 최소공배수 [13241번] https://www.acmicpc.net/problem/13241예제 입력11 1예제 출력11예제 입력23 5예제 출력215예제 입력31 123예제 출력3123예제 입력4121 199예제 출력424079문제 접근입력 한 줄에 두 정수 A와 B가 공백으로 주어짐50%의 입력 중 A와 B는 1,000(10^3)보다 작음다른 50%의 입력의 A와 B는 1,000보다 크고 100,000,000(10^8)보다 작음Java는 long을 사용출력 A와 B의 최소 공배수를 한 줄에 출력문제 해결앞의 문제와 달라진 점은 A와 B가 매우 큰 값이 나올 수 있기 때문에 long을 사용해야 한다는 점결국 똑같은 최소공배수 문제이므로 이번에는 유클리드 호제법을 재귀함수로 구현해볼 것기존 풀이 [메모리 : 14,336 KB /.. 이전 1 2 다음
