kbear   5년 전

안녕하세요.  

4673 셀프넘버 문제를 푸는 중에 체점 기준(?)에 조금 오류가 있을 수 도 있다고 생각합니다. 

제가 뛰어난 실력을 가진 사람은 아니라서 혹시 이런 가능성은 있지 않을까 한번만 생각해봐주시면 감사하겠습니다. 

문제에서 요구하는 것은 10000보다 작은 셀프넘버를 구하는 것입니다. 

먼저, 제가 이 문제의 답을 구한 방식은 

[10001]  크기의 bool 형 배열을 만든 후에 모두 false로 초기화하고, 

생성자가 있는 수일 경우 해당 수와 같은 수를 index로 배열에 접근하여 true 로 만듭니다. 

10000 => 10000 + 1  = 10001 (10000 초과) 이므로, 10000 부터는 답에서 요구하는 범위를 벗어나므로 10000에서 연산을 멈추도록 하였습니다. 

이런 방식으로 셀프 넘버( 배열에서 false 값을 가지고 있는 index) 를 구했을 때, 10000 보다 작은 셀프 넘버는 9993 에서 끝이 아니라, 

08103b9e-c3ce-476c-b32e-2e14a3fae26a

위와 같이 9995, 9997, 9999 가 더 있습니다. 

처음에는 문제에서 제시한 예제 출력에서 전부 나오지 않았다고 생각하고 이대로 답을 제출했는데 틀렸다고 체점이 되어서 오랜 시간 생각해보다가, 예제 출력에 억지로 제 결과를 끼워맞추기 위해서,  for문으로 cout 함수를 사용할 때, i <= 9993 을 탈출 조건으로 주고 제출하였더니 맞았다는 결과가 나왔습니다. 

제가 구현한 알고리즘이 문제가 없다면, 10000 보다 작은 셀프넘버는 9999 까지인데 예제 출력에서도 그렇고, 체점 프로그램도 그렇고 9993 까지가 맞다고 하는것으로 보아, 수정이 필요할 수도 있다고 생각하였습니다. 

물론 제 알고리즘에 문제점이 있고, 9995, 9997, 9999 가 셀프 넘버가 아닐 수도 있을 가능성도 있습니다! 그래서 검토를 부탁드리는 차원에서 의견 남겨봅니다.!

좋은 문제 출제해 주셔서 감사합니다.

kbear   5년 전

아이고, windows.h 헤더와 system 함수는 제 로컬 환경에서 결과 확인용이므로 혹시 실행시켜보시려면 지워야 할 것입니다!

checkmate_2018   5년 전

일단 9999 는 9972로 만들 수 있지 않나요?

jh05013   5년 전

9995 = d(9970)
9997 = d(9971)
9999 = d(9972)

kbear   5년 전

엇 반례가 있네요. 그럼 제 알고리즘이 잘못된거군요. 댓글 달아주셔서 감사합니다! 

 그런데 9993 까지 탈출조건 걸었을때 맞았습니다! 나오는거보면   9993 까지는 정확히 동작하는데 왜 그 이후에는 계산이 정확히 안되는건지 생각해봐야겠네요 .

맞았습니다 받은문제라 이유 찾기가 더 힘들거같군요 ㅋㅋㅋ  

모두 감사합니다! 

kbear   5년 전

break 로 해버리면  아직 10000까지 안가고 for문을 빠져나와서 연산을 끝내버리는군요.. 

9993 이후에 숫자들중에  연산했을 때 10000 넘는 경우가 있다는걸 간과했었습니다.  

감사합니당. 

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