Jonyo Programming

[BOJ 1747(G5)리뷰] N을 입력받아 N보다 크거나 같은 소수 중 팰린드롬인 수를 출력하면 된다. 예를들어 31을 입력받았다면, 31보다 큰 소수중 팰린드롬인 수 101을 출력하면 된다. 이 문제를 풀기위해 크게 두가지 과정을 거쳤다. 1.소수 판별 (에라토스테네스의 체) 2.팰린드롬 판별 처음에 N의 범위가 최대 100만이라 100만까지의 수만 소수판별을 했는데 만약 100만이 입력되었을 경우 100만보다 크거나 같은 소수를 출력해야하므로, 100만보다 크거나 같은 소수 중 팰린드롬 수인 1003001까지 소수판별을 해야 한다. 1003001까지의 소수판별을 한 후에 소수들을 하나의 벡터에 넣고, 입력받은 N의 위치를 lower_bound로 구했다. 이러면 N에서 가장 가까운 소수의 위치를 알 ..

[BOJ 14476(G2)리뷰] N개의 정수가 주어지고 그 중 하나를 뺐을때 남은 정수들의 최소공배수가 최대가 되는 경우를 구해야 한다. 예를들어 [8,12,24,36,48]이라는 정수가 주어졌을 때, 8을 뺀다면 나머지 [12,24,36,48]의 최대공약수가 12로 가장 크다. N의 범위는 4 [12,48] -> [12,12,48] 이런식으로 값을 채워나가게 된다. 그렇다면 이제 [8,12,24,36,48]의 배열에서 가운데에 있는 24라는 값을 뺐을때의 최대 공약수를 구해보자. 24의 index를 3이라 했을때 GCD(LEFT GCD[2],RIGHT[4])가 24를 제외한 나머지 수들의 최대공약수가 되게 된다. 이 알고리즘을 이용하여 N개의 수들을 하나씩 빼가며 최대공약수를 확인하고, 최대공약수가 최..

[BOJ 9020(S1) 리뷰] 소수관련 문제를 풀다가 풀게 된 문제이다. 문제는 설명에 나온대로 2이상의 짝수가 주어지면 그 짝수는 소수 두개의 합으로 이루어진다는것이다. 예를들어 14는 3+11로 이루어지며 10은 5+5로 이루어진다. 만약 짝을 이루는 소수가 두개라면 두 소수간의 차이가 적은것을 출력하면 된다. 나는 소수인지 판별하는 val값을 2부터 n-1까지 증가시키며 만약 val이 소수일경우 n-val의 값이 소수인지 확인 후 그 값이 소수라면 출력하도록 했다. 예를들어 n이 8이라면 2부터 7까지 소수인지 확인을 한다. 3이 소수이므로 isUsed[3]=1이 되고 또 증가하며 5가 소수이고 isUsed[8-5]가 1이므로 두 수를 출력하면 된다. 루프를 돌때마다 확인배열을 초기화시켜주면 가장..