코딩테스트 : 13909번 창문 닫기
| 1 초 | 64 MB | 18973 | 9496 | 8414 | 50.057% |
문제
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
- 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
- 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
- 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)
결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.
입력
첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.
출력
마지막에 열려 있는 창문의 개수를 출력한다.
using System;
public class Solution {
private static void Main()
{
int s = Int32.Parse(Console.ReadLine());
float asnwer = MathF.Truncate(MathF.Sqrt(s));
Console.WriteLine(asnwer);
}
}결국 한 수의 약수의 수가 '홀수' 인 것만 카운트 해야 하니, 제곱이 되는 수들의 수만 세면 된다.
다른 사람의 흥미로운 풀이
그냥 (int)로 형변환 해도 될 듯하다. 버림 함수를 괜히 찾았나.. ?
코딩테스트 : 1929번 소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
흠.... 일단 시간초과 걸릴 것 같지만 해보자
using System;
using System.Text;
public class Solution {
private static void Main()
{
int[] MN = Console.ReadLine().Split().Select(int.Parse).ToArray();
int N = MN[0];
int M = MN[1];
StringBuilder sb = new StringBuilder();
for (int i = N; i <= M; i++)
{
bool isRare = true;
for (int j = 2; j < i; j++)
{
if (i % j == 0)
{
isRare = false;
break;
}
}
if (isRare)
{
sb.AppendLine(i.ToString());
}
}
Console.WriteLine(sb);
}
}역시 시간 초과가 걸린다.
뭔가 소수를 빠르게 판별할 수 있는 규칙을 찾아야 할 것 같다.
소수를 모두 구하고, 그냥 나열하는 방법도 있을 듯 하다.
예를 들어, 2의 배수, 3의 배수, 3의 배수, 4의 배수를 모두 삭제해 버린다거나...
여기서 더해 어떤 소수도 자신의 제곱근보다 큰 수로는 나눠지지 않는다. 왜냐하면 공약수 두 개를 곱해서 소수가 된다면, 제곱근보다 큰 수로 나눠지면 반대쪽 공약수는 이미 지나온(검사한) 수 일테고, 이미 소수인지 아닌지 판별이 끝난 후다.
using System;
using System.Text;
public class Solution {
private static void Main()
{
int[] MN = Console.ReadLine().Split().Select(int.Parse).ToArray();
int N = MN[0];
int M = MN[1];
bool[] numbers = new bool[1000001];
for (int i = 2; i * i<= M; i++)
{
if (numbers[i] == false)
{
// 예를 들어, 4부터 16까지 2의 배수를 모두 제거
// 그 다음은 9부터 16까지 3의 배수를 모두 제거 : 왜 ? 6은 이미 2의 배수라 사라졌음
// 즉 i의 제곱부터 배수를 삭제하면 됨.
for (int j = i*i; j <= M; j += i)
{
numbers[j] = true;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = N; i <= M; i++)
{
if (numbers[i] == false)
{
sb.AppendLine(i.ToString());
}
if (i == 1 )
{
sb.Clear();
}
}
Console.WriteLine(sb);
}
}
'에라토스테네스의 체' 라는 방법이다. 설명은 코드에 주석으로 달아 두었다.
코딩테스트 : 4134번 다음 소수
| 1 초 | 128 MB | 42868 | 11451 | 9128 | 25.103% |
문제
정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.
출력
각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.
using System;
using System.Text;
public class Solution
{
private static void Main()
{
int s = Convert.ToInt32(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s; i++)
{
int n = Int32.Parse(Console.ReadLine());
if (n == 0 || n == 1)
{
sb.AppendLine(n.ToString());
continue;
}
bool stop = true;
while (stop)
{
for (int j = 2; j <= (int)Math.Sqrt(n); j++)
{
if (n % j == 0)
{
n++;
break;
}
if (j == (int)Math.Sqrt(n))
{
sb.AppendLine(n.ToString());
stop = false;
}
}
}
}
Console.WriteLine(sb);
}
}시간 초과가 떴다.
매 번 새롭게 구하는 방식이 아닌듯 하다
using System;
using System.Text;
public class Solution
{
private static void Main()
{
int s = Convert.ToInt32(Console.ReadLine());
StringBuilder sb = new StringBuilder();
bool[] numbers = new bool[4000000001];
for (long i = 2; i * i<= 4000000001; i++)
{
if (numbers[i] == false)
{
// 예를 들어, 4부터 16까지 2의 배수를 모두 제거
// 그 다음은 9부터 16까지 3의 배수를 모두 제거 : 왜 ? 6은 이미 2의 배수라 사라졌음
// 즉 i의 제곱부터 배수를 삭제하면 됨.
for (long j = i*i; j <= 4000000001; j += i)
{
numbers[j] = true;
}
}
}
for (long i = 0; i < s; i++)
{
long n = Convert.ToInt64(Console.ReadLine());
for (long j = n; j <= 4000000001; j++)
{
if (numbers[j])
{
sb.AppendLine(j.ToString());
break;
}
}
}
Console.WriteLine(sb.ToString());
}
}
이번에는 위에서 사용했던 방법을 응용해서 해 보려고 했는데 물어보니 약 4G가 필요하다고 한다..
열심히 하다 보니... 입력이 int로는 못 받아서 overflow문제가 떴던 것 같다.
using System;
using System.Text;
public class Solution
{
private static void Main()
{
int s = Convert.ToInt32(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (long i = 0; i < s; i++)
{
long n = long.Parse(Console.ReadLine());
if (n == 0 || n == 1)
{
sb.AppendLine(2.ToString());
continue;
}
bool stop = true;
while (stop)
{
bool isPrime = true;
for (long j = 2; j*j <= n; j++)
{
if (n % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
stop = false;
sb.AppendLine(n.ToString());
break;
}
n++;
}
}
Console.WriteLine(sb);
}
}다른 사람의 흥미로운 풀이
수를 굳이 1씩 더하면서 비교할 필요 없이, 2씩 더해도 된다. 왜 ? 짝수는 어쩌피 제외되니까 !
혹은 모든 소수는 6K +-1이라는 규칙도 있어 이걸 이용해도 된다.