서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N
개의 창문이 있고 또 N
명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N
번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.
첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)
이 주어진다.
마지막에 열려 있는 창문의 개수를 출력한다.
3
1
24
4
University > 서강대학교 > 2016 Sogang Programming Contest > Master B번
-문제의 오타를 찾은 사람: jaehoo1
-문제를 만든 사람: jerryya211
import java.io.*;
public class Code13909 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.valueOf(br.readLine());
br.close();
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
int answer=(int)Math.sqrt(N);
bw.write(String .valueOf(answer)+"\n");
bw.flush();
bw.close();
}
}
import java.io.*;
import java.util.ArrayList;
public class Code13909 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.valueOf(br.readLine());
br.close();
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
ArrayList<Boolean> window=new ArrayList<>();
window.add(false);//0
window.add(false);//1
for(int i=2;i<=N;i++){
window.add(i,true);
}
for(int i=2;(i*i)<=N;i++){
if (window.get(i)) {
for(int j=i*i; j<=N;j+=i){
window.set(j,false);
}
}
}
int count=0;
for(int i=1;i<=N;i++){
if(!window.get(i)){
count++;
}
}
bw.write(String .valueOf(count)+"\n");
bw.flush();
bw.close();
}
}
이전에 짠 프로그램으로 메모리 초과가 떠서 규칙을 찾아보았다.
즉, sqrt(N)
이 출력되는 것을 확인할 수 있었다!
N=1 .. 1
..
N=3 .. 1
N=4 .. 2
N=8 .. 2
N=9 .. 3
그래서 소스코드를 바꿨다!
약수, 배수와 소수2도 끝냈다!!!!