๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 9020๋ฒˆ : ๊ณจ๋“œ๋ฐ”ํ์˜ ์ถ”์ธก

by nitronium102 2021. 8. 10.

๋ฌธ์ œ

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๊นŒ์ง€๋Š” ์•Œ์•˜์œผ๋‚˜ ๊ฑฐ๊ธฐ์—์„œ ์ž˜๋ชป ์ ‘๊ทผํ•ด์„œ ์กฐ๊ธˆ ์–ด๋ ค์› ๋˜ ๋ฌธ์ œ

๋Œ“๊ธ€