본문바로가기
자유게시판
수학을 주제로 떠들어 보세요!
[잡담] 시즌1 14B에 대한 개인적인 생각들
원파 2022.01.17 09:07 조회 292

* 여기에 적혀있는 내용이 반드시 옳지는 않습니다. 참고만 해주세요 *

 

저는 시즌1 미궁이 오픈된 후로부터 1년 넘는 시간동안 이 문제를 보아왔습니다.

최근 들어 제가 문제를 완전히 잘못 이해하고 있었다는 걸 알게 되었지만요... ㅠㅠ

접근 방법은 화이트가드님의 글에서 더 잘 설명되어 있을 듯 해서, 저는 (코드를 작성한다면) 어떤 알고리즘을 세워야 하는지에 대해서만 조금 얘기해보려고 합니다.

 

0~9 숫자들이 여러 소수들로 나뉘어 들어가야 하는 것이 문제의 조건입니다.

그런데, 3과 7만 해도 37, 73으로 소수가 2가지 가능하죠. 그렇기 때문에, 10개의 수들을 여러 집합으로 나누는 걸 생각해 보겠습니다.

예를 들면 [ 3, 7 ], [ 0, 1, 2, 4, 5, 6, 8, 9 ] 처럼 말입니다.

이제, 각 집합마다 모든 순열을 고려해봅시다. 예시에서는 2! * 8! (각 집합의 크기의 곱) 정도의 가짓수가 있을겁니다.

(0으로 시작하는 경우를 제외하면 조금 작아지긴 합니다)

 

소인수분해의 특성 상 곱해지는 소수가 하나라도 다르다면 원래 수도 다릅니다.

따라서 순열에 대해서 모든 수들이 소수인지 확인하고, 만약 그렇다면 답을 +1 하는 것으로 문제를 해결할 수 있습니다.

 

이렇게 해보면 코드로 계산함에도 불구하고 너무 오래 걸립니다.

자잘한 부분들에서 시간을 줄이고, 소수 판정을 빠르게 한다면 이 문제점은 해결할 수 있습니다.

'소수 판정을 빠르게 한다' 가 쉬워보이지만, 이게 쉬운 내용이 아닙니다.

소수 판정에 관해서 좀 더 자세히 설명해보자면,

 

1)

우선, 가장 간단하게 판정하는 방법은 2~n-1 의 모든 수로 나눠보면 됩니다.

나누어 떨어지는 수가 없으면, n은 소수입니다.

 

2)

n을 x로 나눴을 때 나누어 떨어지면, n을 n/x으로 나누어도 나누어 떨어집니다.

따라서, 2~sqrt(n)까지만 나눠봐도 소수 판정을 할 수 있습니다.

 

3)

(1, 2와 연관은 없으나, 소수와 관련된 내용이라 넣었습니다.)

에라토스테네스 체를 사용하여 미리 소수인지 아닌지를 구해놓을 수도 있습니다.

하지만, 판정해야 하는 수가 최대 약 98억이라는 점을 생각하면, 약 98억 개의 공간을 선언해야 합니다.

우리의 컴퓨터는 이렇게 많은 공간을 여러분에게 내어줄 수 없다고 합니다. 슬프게도 포기해야 하는 방법이군요.

 

4)

(다른 방법이 있을 수도 있습니다. 다만 저는 이렇게 풀었습니다.)

'확률적 소수' 에 대해 생각해봅시다. 이게 뭘까요?

'아마도 이 수는 소수일 것 같아요' 라는 얘기입니다.

'이 수는 무조건 소수에요!' 라고 할 수는 없지만, 높은 확률로 정확하면서 동시에 빠른 알고리즘이 있을까요?

밀러-라빈 소수판별법이라는 것이 있습니다. https://rebro.kr/46 를 참고해 보실 것을 추천드립니다.

이 판별법을 사용하면, 꼭 필요하던 빠른 소수판정을 해낼 수 있습니다.

 

------

 

그래서 이 문제가 쉽냐고 한다면, 저는 아니라고 생각합니다.

문제 자체부터 이해하는게 어렵고,(1년넘게 잘못 이해하고 있던 저의 케이스) 이해했다고 하더라도 옳은 접근을 떠올리기 어렵습니다.

하지만, 접근까지 하셨다면 코드를 짜는건 그렇게 어렵지 않다고 생각합니다.

 

 저의 결론은 이렇습니다.

 

화이트가드님을 존경합시다!

orz orz orz orz

여담) 저는 14번을 푼 뒤 화이트가드님 방향으로 3번 절했습니다.

첫 댓글의 주인공이 되어 보세요!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911