๋ฌธ์
1๋ณด๋ค ํฐ ์์ฐ์ ์ค์์ 1๊ณผ ์๊ธฐ ์์ ์ ์ ์ธํ ์ฝ์๊ฐ ์๋ ์์ฐ์๋ฅผ ์์๋ผ๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 5๋ 1๊ณผ 5๋ฅผ ์ ์ธํ ์ฝ์๊ฐ ์๊ธฐ ๋๋ฌธ์ ์์์ด๋ค. ํ์ง๋ง, 6์ 6 = 2 ร 3 ์ด๊ธฐ ๋๋ฌธ์ ์์๊ฐ ์๋๋ค.
๊ณจ๋๋ฐํ์ ์ถ์ธก์ ์ ๋ช ํ ์ ์๋ก ์ ๋ฏธํด๊ฒฐ ๋ฌธ์ ๋ก, 2๋ณด๋ค ํฐ ๋ชจ๋ ์ง์๋ ๋ ์์์ ํฉ์ผ๋ก ๋ํ๋ผ ์ ์๋ค๋ ๊ฒ์ด๋ค. ์ด๋ฌํ ์๋ฅผ ๊ณจ๋๋ฐํ ์๋ผ๊ณ ํ๋ค. ๋, ์ง์๋ฅผ ๋ ์์์ ํฉ์ผ๋ก ๋ํ๋ด๋ ํํ์ ๊ทธ ์์ ๊ณจ๋๋ฐํ ํํฐ์ ์ด๋ผ๊ณ ํ๋ค. ์๋ฅผ ๋ค๋ฉด, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7์ด๋ค. 10000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๋ชจ๋ ์ง์ n์ ๋ํ ๊ณจ๋๋ฐํ ํํฐ์ ์ ์กด์ฌํ๋ค.
2๋ณด๋ค ํฐ ์ง์ n์ด ์ฃผ์ด์ก์ ๋, n์ ๊ณจ๋๋ฐํ ํํฐ์ ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ง์ฝ ๊ฐ๋ฅํ n์ ๊ณจ๋๋ฐํ ํํฐ์ ์ด ์ฌ๋ฌ ๊ฐ์ง์ธ ๊ฒฝ์ฐ์๋ ๋ ์์์ ์ฐจ์ด๊ฐ ๊ฐ์ฅ ์์ ๊ฒ์ ์ถ๋ ฅํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ ์ง์ n์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์ ์ฃผ์ด์ง n์ ๊ณจ๋๋ฐํ ํํฐ์ ์ ์ถ๋ ฅํ๋ค. ์ถ๋ ฅํ๋ ์์๋ ์์ ๊ฒ๋ถํฐ ๋จผ์ ์ถ๋ ฅํ๋ฉฐ, ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํ๋ค.
์ ํ
- 4 โค n โค 10,000
ํ์ด
์ด ๋ฌธ์ ์ ํต์ฌ์ N/2 - i์ N/2 + i๊ฐ ๋ ๋ค ์์์ฌ์ผ ํ๋ค๋ ๊ฒ์ด๋ค. (N - i์ i์ ๊ด๊ณ๋ก๋ ์๊ฐํ ์ ์๋ค)
https://cryptosalamander.tistory.com/30์ ํ์ด์์ ๋ฐฐ์ด์ ์ ์ฅํ๋ ๋ถ๋ถ์ ์ฐธ๊ณ ํ๋ค! ๋๋ MAX=10000์ผ๋ก ๋๊ณ ๋๋ฆฌ๊ฑฐ๋ ๋งค ์ ๋ ฅ๋ง๋ค for๋ฌธ์ผ๋ก ์ฒ๋ฆฌํ๋๋ฐ, ์์ ์ฒ์๋ถํฐ ํ ๋ฒ์ ๋ฐ์์ ๋ฐฐ์ด์ ๋ฃ๊ณ ๊ณ์ฐํ๋ ๋ฐฉ์์ด ๋ ๊น๋ํ ๊ฒ ๊ฐ๋ค!
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int T, max=0;
cin >> T;
// ํ๊บผ๋ฒ์ ๋ฐ์์ ๋ฐฐ์ด์ ์ ์ฅ
int *num = new int[T];
for (int i = 0; i<T; i++){
cin >> num[i];
if (max < num[i])
max = num[i];
}
// ํ
์คํธ ์ผ์ด์ค์ ์ต๊ณ ๊ธธ์ด๊น์ง bool ๋ฐฐ์ด ์์ฑ
bool isPrime[max+1];
fill_n(isPrime, max+1, true);
isPrime[0] = false;
isPrime[1] = false;
// ์์ ํ์
for (int i=2; i<=sqrt(max); i++){
if (isPrime[i]){
for (int j=i*2; j<=max; j+=i)
isPrime[j] = false;
}
}
// ๊ณจ๋๋ฐํ ํํฐ์
์ถ๋ ฅ -> N/2 + i์ N/2 - i๊ฐ ๋ชจ๋ ์์๊ฐ ๋๋๋ก
for (int i=0; i<T; i++){
for (int j=num[i]/2; j>0; j--){
if (isPrime[j] && isPrime[num[i]-j]){
cout << j << " " << num[i]-j << "\n";
break;
}
}
}
}
N/2๊น์ง๋ ์์์ผ๋ ๊ฑฐ๊ธฐ์์ ์๋ชป ์ ๊ทผํด์ ์กฐ๊ธ ์ด๋ ค์ ๋ ๋ฌธ์
'โจ Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค/C++] 3009 : ๋ค ๋ฒ์งธ ์ (0) | 2021.08.12 |
---|---|
[๋ฐฑ์ค/C++] 1085๋ฒ : ์ง์ฌ๊ฐํ์์ ํ์ถ (0) | 2021.08.12 |
[๋ฐฑ์ค/C++] 4948๋ฒ : ๋ฒ ๋ฅดํธ๋ ๊ณต์ค (0) | 2021.08.08 |
[๋ฐฑ์ค/C++] 1929๋ฒ : ์์ ๊ตฌํ๊ธฐ(์๊ฐ ์ด๊ณผ, ์๋ผํ ์คํ ๋ค์ค์ ์ฒด) (0) | 2021.08.07 |
[๋ฐฑ์ค/C++] 11653๋ฒ : ์์ธ์๋ถํด (0) | 2021.08.07 |
๋๊ธ