Viento   7년 전

1291 문제를 풀고 있었는데요.  제가 생각한 요구사항대로 답을 만들었는데 계속 틀렸다고 나오네요.


문제의 내용은 굉장히 길기 때문에 전문은 링크를 첨부하고 요약을 하도록 하겠습니다

링크 : https://www.acmicpc.net/problem/1291

이 문제에서 가장 중요한 내용은 배성경 조교의 숫자 분류 체계인데요.


배성경 조교의 숫자 분류 체계는 다음과 같다. 배성경 조교는 이면수와 임현수라는 숫자를 분류하는 방법을 생각해 내었다.
어떤 숫자가 “이면수”이기 위해서는 다음과 같은 조건을 만족해야 한다. 메갈루젼 문명의 자연수 분류방식에 있던 “신이 태초부터 완성시켜져 있었던 계급[어비스 오엘 우테(absolute)]”에 속해 있어야 하고, 각 자릿수의 합이 홀수여야 한다.
또한 어떤 숫자가 "임현수“이기 위해서는 그 숫자가 자체가 월드 문명의 chicken number 혹은 starcraft number이거나 합성수이면서 소인수 분해를 했을 때 소인수의 종류의 개수가 짝수개 이어야 한다.
조교 배성경은 자신의 이름을 역사에 남기기 위해서 이면수도, 임현수도 아닌 숫자를 “성경수”라고 정의했다.
  어떤 숫자 N이 주어지면, 그 숫자를 분석한 결과를 출력하도록 한다.
만약 그 숫자가 이면수라면 “1”라고 출력하고, 그 숫자가 임현수라면 “2”라고 출력한다. 주어진 수가 이면수도 임현수도 아닐 수 있는데 그럴 경우에는 배성경 조교가 정의한 대로 “3”를 출력한다. 혹은, 그 숫자가 이면수이면서 임현수이면 “4”를 출력하도록 한다.

이렇다고 합니다.

Absolute 계급에 속하는 메갈루젼 문명의 숫자는

숫자 4는 위대한 숫자 1과 시작의 숫자 3의 합으로 “완벽하다”라는 의미를 갖는 완벽한 숫자들이다. 그와 동시에, 이 완벽한 숫자들과 태초의 숫자들(2와 3)의 합으로 표현되는 숫자들, 즉 6, 7, 8, 9, 10 ... 들 역시 포함해서 “처음부터 완벽했던, 태초부터 존재했던”이라는 의미인 “완전[피-얼프 에크트(perfect)]” 혹은 “신이 태초부터 완성시켜져 있었던 계급[어비스 오엘 우테(absolute)]”이라고 부른다.

라고 합니다. 즉 완벽한 숫자들 4, 그리고 4 + 태초의 숫자들로 완성가능한 6,7,8,9,10.. :: N>5 범위의 수를 얘기하는 것 같습니다.

이면수이기 위한 조건은 각 자리수를 합했을때 홀수 + Absolute 계급의 숫자여야 한다고 하는데요.

이에 해당하는 숫자들은 N>5 이고, 각 자리수를 합했을때 홀수인 숫자인 것 같습니다.

그리고 임현수는 월드 문명의 chicken num(=4), starcraft num(=2), 합성수이면서 수인수 종류의 개수가 짝수 개인 수 중에 하나에 해당되면 되는 숫자인 것 같습니다.


성경수는 이면수도 아니고 임현수도 아닌 수라고 합니다.

이면수는 N>5 && (N/1000+N/100+N/10+N%10)%2==1 인 수이고 (N의 범위가 0~2700임)

임현수는 N=2 || N=4 || 합성수이며 소인수 종류가 짝수가지인 수

성경수는 !이면수 && ! 임현수

이고

이면수는 1

임현수는 2

성경수는 3

둘다는 4 를 출력해달라고 합니다.


그래서 아래와 같이 짜봤는데 문제가 없는 것 같은데 계속 틀린다고 나옵니다. 

제 생각엔 제가 이면수, 임현수의 범위를 잘못 안 것이 아니라면 틀릴 이유가 없는 것 같아서요..

도움을 부탁드립니다.

dlwodnsdl   7년 전

1은 합성수가 아니지만 저 코드대로라면 stack의 값이 0이여서 소인수가 짝수개인 합성수로 분류됩니다.

Viento   7년 전

dlwodnsdl 님의 명쾌한 답 덕에 해결되었습니다 ㅎㅎ 감사합니다.

당장은 순환문에 들어가기 전에 N 자체가 1인지 확인하는 조건문만 추가해서 해결했지만 

소인수 종류를 구하는 더 좋은 방법을 생각해봐야 겠습니다. 감사합니다.


dlwodnsdl   7년 전

간단하게는 소인수 분해하실때 조건문을 p*p<=n으로 하시고, 끝났을때 n이 1이아니면 소인수의 개수에 +1을 해주시면 좀더 빠른 소인수구하기가 가능합니다.

Viento   7년 전

헉 한번 해봐야 겠습니다 ㅎㅎ 알려주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.