본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[국가수리과학연구소] 국21. 내맘대로 숫자 레시피
수학동아 2018.09.03 17:25 조회 3

 

국가수리과학연구소의 21번째 문제입니다.

 

문제1 

아래 숫자 5개를 전부 한 번씩만 쓰고, 사칙연산과 괄호만 이용해 숫자 38을 만들어라.

 

1   4   5   5   5 

 

 

문제2

1 이상, 9 이하의 숫자 5개를 고른 뒤, 이 숫자 5개로 문제1과 같은 방법으로 1부터 연속한 자연수를 가장 많이 만들 수 있는 방법은 무엇일까? 이때, 자연수는 1부터 연속해서 어디까지 만들 수 있을까? 예를 들어, 1 다섯 개로는 1부터 6까지의 수는 만들 수 있지만, 7과 8은 만들 수 없다.

 

※오타를 수정합니다.

문제2 4번째 줄에 '1부터 7까지의 수'가 아니라, '1부터 6까지의 수'입니다.

 

※알립니다.

①누군가 친구가 소문제 1번을 해결했어요. 다들 정답을 확인해 보세요!! 

②소문제 2번은 수돌이 친구가 최초로 풀고, 이어 수학자누군가 친구가 잇달아 풀었습니다. 문제 특성상 3명이 공동으로 푼 걸로 인정하겠습니다. 프로그래밍으로 문제를 해결할 때 어떻게 풀이를 검증하는지 잘 알아두세요!!laugh

  •  
    프로벤젠 Lv.1 2018.09.03 18:22

    문제 1 증명과정

     

    /

    mod 5로 보자.

    38은 mod 5로 3이다.

    1,4,5,5,5로 3 (mod 5)를 만들 수 있는 것은 (4-1)밖에 없다.

    즉 3,5,5,5로 38을 만드는 것과 동일한데,

    이는 불가능하다.

    /

     

    혹시 이 증명에 오류가 있나요?

    댓글 작성하기 좋아요1 댓글수4
    •  
      모두다같이 Lv.1 2018.09.04 22:05

      저두 3(mod5)인 수가 4-1 = 3 뿐인 줄 알았는데

      5×5-1-(5-4) = 23도 있긴 하네요!

      좋아요0
    •  
      프로벤젠 Lv.1 2018.09.06 23:02

      아 그럴수도 있겠네요.

      좋아요0
    •  
      페르마 Lv.1 2018.09.09 20:39

      그런데 mod 5가 23이라고 가정해도 38을 만드는 것은 불가능한 것 같습니다

      좋아요0
    •  
      POLYMATH Lv.1 2019.08.04 11:56

      (5-1/4)*(5+5) 맞나요?

      좋아요0
  •  
    프로벤젠 Lv.1 2018.09.03 18:28

    그런데 1 다섯 개로 7을 어떻게 만들죠?

    댓글 작성하기 좋아요1 댓글수2
    •  
      수학장 Lv.1 2018.09.03 23:29

      문제가 잘못 된 것 같네요

      좋아요0
    •  
      킬러퀸 Lv.4 2018.09.04 09:28

      앗, 오타 죄송합니다! 백진언 연구원님께 확인한 결과 7이 아닌 6입니다!

      좋아요0
  •  
    수학장 Lv.1 2018.09.03 23:25

    1번 문제는 금방 풀릴 것 같은데...

    댓글 작성하기 좋아요0 댓글수1
    •  
      바람개비 Lv.1 2018.09.05 01:19

      불가능합니다.

      좋아요0
  •  
    아인수타인 Lv.1 2018.09.04 00:14

    1 두개를 사용해 11로 만드는 게 가능한가요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      프로벤젠 Lv.1 2018.09.04 17:02

      안될 것 같은데요?

      1 다섯 개로 8을 만들 수 없다고 문제에 나와있는데,

      만약 1 두개로 11을 만들 수 있다고 한다면,

      11-1-1-1로 8을 만들 수 있으니 문제 조건에 모순되어 안될 것 같습니다.

       

      그리고 직관적으로 안될 것 같은 느낌이 강하게 나는데요?

       

      좋아요0
  •  
    시그마 Lv.1 2018.09.04 11:59

    문제 1 가능한거죠?

     

    댓글 작성하기 좋아요0 댓글수2
    •  
      아인수타인 Lv.1 2018.09.04 15:03

      만약 불가능하다면 문제 1에서 '아래 숫자 5개를 전부 한 번씩만 쓰고, 사칙연산과 괄호만 이용해 숫자 38을 만들 수 있을까?' 라고 묻지 않았을까요?

      좋아요0
    •  
      프로벤젠 Lv.1 2018.09.04 17:04

      저는 느낌상 불가능할 것 같은데요.

      가능하다면 이를 문제로 내지는 않았을 것 같아요. 

      좋아요0
  •  
    아인수타인 Lv.1 2018.09.04 15:42

    엥, 근데 맨 위쪽에 대한수학회가 아니라 국가수리과학연구소 아닌가요? (대괄호 안에)

    댓글 작성하기 좋아요0 댓글수1
  •  
    모두다같이 Lv.1 2018.09.04 20:04

    39,37,36,35,34같은건 만들겠는데 38은 아직 못만들었네요ㅠ

    41- (5+5)/5 = 39

    51-(4+5+5) = 37

    55-4×5+1 = 36

    155÷5+4 = 35

    54-(5+15) = 34

    댓글 작성하기 좋아요0 댓글수4
    •  
      수학장 Lv.1 2018.09.04 21:29

      4랑 5를 45로 만드는 등의 연산은 불가능합니다

      좋아요0
    •  
      모두다같이 Lv.1 2018.09.04 21:47

      14를 1와 4한 번씩 썼다고 보면 안된단 거군요. 알겠습니다.

      좋아요0
    •  
      수학장 Lv.1 2018.09.04 22:08

      근데 그런 말은 안 쓰여 있어서 만약 문제 2의 8은 만들 수 없다.라는 말이 오타라면 될 것 같습니다. 이건 출제자분이 직접 언급해주셔야 할 것 같네요

      좋아요0
    •  
      모두다같이 Lv.1 2018.09.04 22:24

      앗 중간에 아인수타인님 댓글 밑에 걸린 프로벤젠님말대로 1 두개를 붙여 11로 만드는 방식은 아예 안되네요. 제가 프로벤젠님 댓글을 놓쳤군요..

      좋아요0
  •  
    킬러퀸 Lv.4 2018.09.05 09:21

    출제자 님께 등판을 요청했지만, 바쁘신 관계로 의견만 전달!

     

    ①숫자 1, 2를 12로 붙여쓰는 건 불가!angry

    ②문제 마지막에 "8은 만들 수 없다"는 오타가 아님!

    (단, 연속된 숫자를 못만든다는 의미를 강조하기 위해 8 앞에 7을 추가하겠습니다. angel)

    댓글 작성하기 좋아요0 댓글수0
  •  
    수학장 Lv.1 2018.09.05 21:21

    근데 문제 둘 다 컴퓨터로 풀면 쉬울 것 같은데

    손으로 푸는 걸 원하는 건가요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      킬러퀸 Lv.4 2018.09.06 09:28

      반드시 그런 건 아니예요!

      출제자 님도 "프로그래밍 연습도 할겸, 프로그래밍을 이용해 문제를 해결하는 것도  좋을 것 같다"고 전했답니다.laugh

      좋아요0
  •  
    모두다같이 Lv.1 2018.09.06 22:44

    1,2,3,4,5를 뽑으면 괄호와 사칙연산을 통해 1부터 연속으로 얼마까지 만들 수 있을까요?

    댓글 작성하기 좋아요0 댓글수7
    •  
      프로벤젠 Lv.1 2018.09.06 23:27

      1=3÷(1+2)×(5-4)

      2=(4-(5-3))÷2+1

      3=5×2-4-3×1

      4=4×(5-3-2+1)

      5=5×((3+2)×1-4))

      6=(5+1)×(2+3-4)

      7=(5+2)×(4-3×1)

      8=(5+3)×(4-2-1)

      9=(5+4)×(3-2×1)

      10=(5+4+1)×(3-2)

      11=(5+4+3-2+1)

      12=(5+4+3)×(2-1)

      13=(5+4+3+2-1)

      14=(5×3)-(3-2×1)

      15=(5+4+3+2+1)

      16=(5×4-3-(2-1))

      17=(5×4-3×(2-1))

      18=(5×4-3+2-1)

      19=(5×4-(3-2×1))

      20=(5×4×(3-2×1))

      21=(5×4+(3-2×1))

      22=(5×4+(3+1-2))

      23=(5×4+3×(2-1))

      24=(5×4+3+2-1)

      25=(5×(4+1)×(3-2))

      26=(5×(4+1)+(3-2))

      27=(5×(4+2)-3×1)

      28=(5×(4+2)-(3-1))

      29=(5×(3+2)+4×1)

      30=(5×(4+1)+3+2)

      31=???

      좋아요0
    •  
      프로벤젠 Lv.1 2018.09.06 23:31

      동참해 주실분 구합니다.

      그런데 예상보다 많이 나오네요...

      프로그래밍 등 다른 방법이 필요할 것 같습니다.

      좋아요0
    •  
      모두다같이 Lv.1 2018.09.07 15:09

      14에 3이 2개 있으셔서 14 = 3 x 4 + (5-2-1)

      로 다르게 나타내봤어요.

      그리고 31부터는..

      31 = (5+2) x 4 + 3 x 1

      32 = (5+2) x 4 + 3 + 1

      33 = (5+3) x 4 + 2 - 1

      34 = (5+3) x 4 + 2 x 1

      35 = (5+3) x 4 + 2 + 1

      36 = ( 5 + 3 + 2 - 1 ) x 4

      37 = 2 x 4 x 5 - 3 x 1

      38 = (5 + 3) x (4 + 1) - 2

      39 = (1+5) x (4+2) + 3

      40 = (4+2-1) x (5 +3)

      41 = (2x5+4) x 3 - 1

      42 = 5 x (4+3+1) + 2

      43 = (2x5 +4) x 3 + 1

      44 = (5 x 4 +2) x(3 - 1)

      45 = (3x1 +2) x (5+4)

      46 = 2 x (4 x 5 + 3 x 1)

      47 = 2 x (4 x 5 + 3) + 1

      48 = 4 x (5 x 2 + 3 - 1)

      49 = (3 + 4) x (2 + 5) x 1

      50 = 5 x (1+2+3+4)

      51 = 3 x (4 x 5 - 1 - 2)

      52 = 4 x (1 x 2 x 5 + 3)

      53 = 5 x (3 x 4 - 1) - 2

      54 = (5 + 4x1) x 3 x 2

      55 = 5 x (3 x 2 + 4 + 1)

      56 = (3 + 4) x (1 + 2 + 5)

      57 = 3 x 4 x 5 - 2 - 1 

      58= 3 x 4 x 5 - 2 x 1

      59 = 3 x 4 x 5 - 2 + 1

      60 = (1 + 4 + 5) x 3 x 2

      61 = 3 x 4 x 5 + 2 - 1

      62 = 3 x 4 x 5 + 2 x 1

      63 = 3 x 4 x 5 + 2 + 1

      64 = (3 + 5) x (1 x 2 x 4)

      65 = (3 + 5) x 2 x 4 + 1

      66 = (1 + 5) x (4x2 +3)

      67 = ??

      일일이 나열하면서 문제에 도움이 될 성질이 무엇일지 찾아야겠단 생각이 들어요..

       

      1번문제는 불가능할 것 같단 느낌만 드는데.. 불가능한 이유를 찾아보려해요.

      좋아요0
    •  
      KSRA Lv.1 2018.09.07 18:08

      혹시 1,2,3,4,5 로 74나 76을 만들 수 있나요?

      1~73, 75, 77은 만들 수 있어요.

      좋아요1
    •  
      모두다같이 Lv.1 2018.09.07 20:57

      74 = (5+1) x 4 x 3 + 2를 찾았어요.

      좋아요0
    •  
      아인수타인 Lv.1 2018.09.08 15:57

      권순용님이 물어보셨던 건 아니지만 78 = (3 + 1) x 5 x 4 - 2도 찾았어요.

      좋아요0
    •  
      아인수타인 Lv.1 2018.09.09 01:23

      요 대댓글과 별개지만 1,2,3,4,5말고 3,4,5,7,9를 쓴다면 76도 가능합니다.

      76=3 x 4 x 5 + 7 + 9

      좋아요0
  •  
    모두다같이 Lv.1 2018.09.07 15:56

    문제2번 1~9중 5개 고를 때 1,2,3,4,5같이 서로다른 경우 말고도

    1 4 5 5 5처럼 서로 같은 수를 여러 번 골라도 괜찮은건가요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      아인수타인 Lv.1 2018.09.09 01:06

      다시 보니까, 문제 자체에 1 다섯 개로는이라고 예가 나와 있어 중복도 가능할 것 같아요.

      좋아요0
  •  
    아인수타인 Lv.1 2018.09.08 15:51

    1,2,3,4,5뿐만 아니라 2,5,3,8,6등 5!=120가지(중복이 가능하다면 55=3125가지)나 살펴봐야 합니다. 제 생각에 손으로 계산하는 건 영 아니라고 보는데요.

    댓글 작성하기 좋아요0 댓글수2
    •  
      프로벤젠 Lv.1 2018.09.08 17:54

      이번문제가 접근은 쉽지만 푸는게 어렵네요.

      좋아요0
    •  
      페르마 Lv.1 2018.09.09 20:45

      55는 3125가지이니 프로그래밍이 필요한 건 맞는 것 같습니다..

      좋아요0
  •  
    muse Lv.1 2018.09.08 17:24

    1번에 39는 여러 방법이 있는데 38은 어렵네요.

    뭔가 가능할 것 같은데...

    댓글 작성하기 좋아요0 댓글수4
    •  
      muse Lv.1 2018.09.08 17:32

      문제와는 별개로 루트를 쓰면 가능합니다.

      4x(5+5)-sqrt(5-1)

      좋아요0
    •  
      아인수타인 Lv.1 2018.09.09 01:32

      처음엔 문제에서 '38을 만들어라'라고 해서 가능할것 같았더니 지금은 왠지 가능하다는 걸 보이기보단 불가능하다는 걸 증명하는게 나을 것 같아요.(나중에 댓글이 어떻게 달릴지 몰라 확신할 순 없지만)

      좋아요0
    •  
      math Lv.1 2018.09.09 10:48

      루트를 쓰면 이렇게도 38을 만들 수 있죠.

      (5*5-5-1)*sqrt(4)

      좋아요0
    •  
      sincostan Lv.1 2018.09.11 17:03

      일단 경우의수를 나눠 생각하는거 어때요?

      좋아요0
  •  
    sincostan Lv.1 2018.09.11 16:25

    아무래도  괄호가  힌트인 것 같은데요

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      sincostan Lv.1 2018.09.11 17:00

      문제1번 불가능한거 같은데

      좋아요0
  •  
    muse Lv.1 2018.09.11 20:39

    계산해 보니 수의 배치 방법 20가지, 연산기호 배치 4^4=256가지, 괄호의 배치 방법 42가지로 총 약 21만 가지입니다.

    코딩으로 해결하기 충분한 문제네요.

    댓글 작성하기 좋아요0 댓글수4
  •  
    ln -1=pi*i Lv.1 2018.09.11 22:21

    처음 수를 x1 , y1 으로 시작하고 이 두가지로 할 수 있는 연산이 6가지니깐 처음 연산한 결과를 x2 다른 숫자를 y2 로 했을 때 이를 x4 , y4 까지 가게 해야하니  64 가지가 되고 이는 1296이니 1296가지 이네요. (문제 1)

    댓글 작성하기 좋아요0 댓글수1
    •  
      muse Lv.1 2018.09.11 22:36

      괄호가 있잖습니까.

      좋아요0
  •  
    sincostan Lv.1 2018.09.11 23:06

    그럼 1번문제는 답이 나온 건가요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    muse Lv.1 2018.09.12 13:26

    나올 수 있는 괄호의 경우를 저는 42가지로 분류했거든요. (N은 수, O는 연산자)

    가짓수가 더 있을까요?

    "NONONONON", "(NON)ONONON", "(NONON)ONON", "(NONONON)ON", "NO(NON)ONON",
    "NO(NONON)ON", "NO(NONONON)", "NONO(NON)ON", "NONO(NONON)", "NONONON(ON)",
    "((NONON)ON)ON", "((NON)ONON)ON", "(NO(NONON))ON", "(NO(NON)ON)ON",
    "(NONO(NON))ON", "((NON)ON)ONON", "(NO(NON))ONON", "(NONON)O(NON)",
    "(NON)O(NONON)", "(NON)O(NON)ON", "(NON)ONO(NON)",
    "NO((NONON)ON)", "NO((NON)ONON)", "NO(NO(NONON))", "NO(NO(NON)ON)", "NO(NONO(NON))",
    "NO((NON)ON)ON", "NO(NO(NON))ON", "NO(NON)O(NON)", "NONO((NON)ON)",
    "(((NON)ON)ON)ON", "((NO(NON))ON)ON", "((NON)O(NON))ON",
    "((NON)ON)O(NON)", "(NO((NON)ON))ON", "(NO(NO(NON)))ON", "(NO(NON))O(NON)",
    "(NON)O((NON)ON)", "NO(((NON)ON)ON)", "NO((NO(NON))ON)", "NO((NON)O(NON))",
    "NO(NO((NON)ON))"
     

     

    댓글 작성하기 좋아요0 댓글수3
    •  
      sincostan Lv.1 2018.09.12 15:27

      제 생각도 이게 끝인 거 같네요

      좋아요0
    •  
      누군가 Lv.1 2018.09.13 23:41

      연산기호 4가지의 연산순서만 정하면 되기 때문에 4!=24가지만 따져도 됩니다.

      좋아요0
    •  
      muse Lv.1 2018.09.15 01:27

      그런 좋은 방법이!

      좋아요0
  •  
    프로벤젠 Lv.1 2018.09.13 17:03

     

    /

    mod 5로 보자.

    38은 mod 5로 3이다.

    5를 곱하면 mod5로 0이 된다.

    또한 5를 더하는 것 또한 mod5로 변화를 주지 않는다.

    따라서 1,4만으로 3을 만들어야한다.

    이때 1,4,5,5,5로 3 (mod 5)를 만들 수 있는 것을 두 종류로 나누어 확인해보자

    1) 3을 만들때 5를 사용하지 않을 경우

    (4-1)이 유일하다.

    3,5,5,5로 38을 만들 수 없다.

     

    2) 3을 만들때 5를 사용할 경우

     

    1,4를 (5-4)혹은 (5-1)로 사용하거나

    5에 1,4를 더한 후 곱해야 의미가 있다.

     

    2-a-1) (5-4)사용

    1,1,5,5 사용하는 것과 동일.

    38은 만들 수 없다.

     

    2-a-2) (5-1)사용

    4,4,5,5 사용하는 것과 동일

    38은 만들 수 없다.

     

    2-a-3) (5-1), (5-4) 사용

    1)과 동일

     

    2-b-1) (5-4)와 곱할 때

    1,5,5 사용하는 것과 동일

    38은 만들 수 없다.

     

    2-b-2) (5+4)와 곱할때

    1,9,5,5 사용하는 것과 동일 (9는 곱하는 용도)

    38은 만들 수 없다.

     

    따라서 불가능하다.

    /

    처음 이용한 방식을 응용해 보았습니다.

     

    나중에 시간날때 완성시키겠습니다.

    오류 지적해 주시면 감사하겠습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    서러서차 Lv.1 2018.09.13 19:17

    nCr도 괄호라고 치나요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    누군가 Lv.1 2018.09.13 23:37

    문제1번 답

    (4-(1/5))*(5+5)

    스크래치로 모든 경우의수를 확인하여 찾았습니다.

    https://scratch.mit.edu/projects/246053946/

    댓글 작성하기 좋아요1 댓글수5
    •  
      킬러퀸 Lv.4 2018.09.14 09:38

      누군가 친구 정다아아아아아아압!surprise 부분해결 딱지 부착입니다!

      좋아요0
    •  
      프로벤젠 Lv.1 2018.09.14 20:58

      와우! 이런 방법이 있었군요!

      답이 없을것 같았는데, 이런 답이 있었네요.

      놀랍습니다!

      좋아요0
    •  
      muse Lv.1 2018.09.15 01:26

      몇 줄만 고치니 이 네 가지 나오네요.

       

      (4-1/5)*(5+5): 38.00000
      (5+5)*(4-1/5): 38.00000
      (4-(1/5))*(5+5): 38.00000
      (5+5)*(4-(1/5)): 38.00000

       

      보니까 아예 소수 계산이 안 되고 있었네요. 아쉬워라... (그리고 괄호 쌍 한 가지 더 있었네요.)

      좋아요0
    •  
      킬러퀸 Lv.4 2018.09.20 10:43 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      누군가 Lv.1 2018.09.23 01:17 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    누군가 Lv.1 2018.09.14 00:40

    2번의 모든 경우를 계산 해볼 수 있는 코드는 있으나 최적화는 전혀 되어있지 않아 다 계산 하려면 100시간 정도( 소요될 것 같습니다...........(숫자 배열 하나당 6초,중복배열수9^5,(6×9^5)/3600=~=100)

    https://scratch.mit.edu/projects/246059976/

    댓글 작성하기 좋아요0 댓글수2
    •  
      뉴턴의 사과 Lv.1 2018.09.14 15:41

      누군가가 이걸 c나 python으로 바꿔주시면 좋을 것 같은데욥. 저는 스크래치 코드를 이해 못해서 못하겠습니다...

      좋아요0
    •  
      누군가 Lv.1 2018.09.17 01:49

      같은 숫자 조합에 다른 배열이 있다는 것을 빼먹었네요... 숫자 순서가 정해져있을 때는 78262로 80까지 만드는 경우가 가장 긴 경우입니다.

      좋아요0
  •  
    수돌이 Lv.1 2018.09.15 03:30

    2번문제 c프로그래밍을 이용한 풀이

    먼저 고려해야 할 점: 숫자 다섯 개의 조합 (a,b,c,d,e)는 일반성을 잃지 않고 a<=b<=c<=d<=e로 가정해도 된다. (<=는 같거나 크다를 의미한다)

    그리고 (a,b,c,d,e)로 만들 수 있는 수를 찾을 때 (a,b,c,d,e)의 순열에 대해서 고려하므로 (즉, (1,1,1,1,2)의 순열은 2가지, (1,3,4,5,7)의 순열은 120가지..)

    a,b,c,d,e가 각각 1이상 9이하인 9^5=59,049가지의 경우는 정확히 한 번 이 시행에 등장한다.

    1) 따라서 순서가 정렬되어 있는 (a,b,c,d,e)의 순열의 개수의 총합은 59,049가지이다.

    2) 그리고 수와 수 사이 4^4=256가지의 연산기호를 넣을 수 있고,

    3) 괄호를 이용한 연산순서의 조정은 다음과 같이 생각해도 된다. 한 번의 연산은 인접한 두 수를 묶어서 하나로 만드는 것이다. 즉 2+3*7+4-3에서 7+4에 연산을 실행하면 2+3*11-3이 되는 것이다. 네 번의 연산을 통하여 다섯 개의 수를 하나로 만들 수 있다. (그래서 연산기호가 총 4개)  4개의 연산자를 어떤 순서로 실행할 것인지 결정하는 것은 4!=24가지가 존재한다. 그리고 그것은 괄호를 통하여 무조건 구현 가능하다. 예를 들어서, 1+2-3*4/5에서 -,*,+,/순서로 연산을 진행한다면 그 순서대로 괄호를 묶어 ((1+((2-3)*4))/5)라는 식이 되는 것이다.

    따라서 총 가지수는 362,797,056가지이고, 각 가지수마다 아래의 코드에 의하면 프로그램 내 16~24회의 연산이 필요하다. 따라서 총 연산횟수는 약 72억이므로 예상 소요 시간은 약 72초라고 할 수 있다.

     

    #include <stdio.h>
    #include <algorithm>
    using namespace std;

    //프로그램의 시작. next_permutation이라는 특별한 함수를 사용하기 위해서 #include <algorithm>을 선언해준다.

    struct fraction{
        int u;
        int d;
    };

    //소수를 표현하는 float를 이용할 경우 두 변수가 같은지 판별하는데 있어서 오류 위험이 있으므로(반올림) 분수를 구현하는 구조체를 쓰도록 한다. 구조체란, 프로그램 작성자가 원하는 형태의 변수를 만들어 사용할 수 있는 것으로, 여기서는 분모를 표현하는 정수 u, 분자를 표현하는 정수 d를 묶어서 하나의 변수로 사용한다.

    struct fraction cal_table[5];
    int oper_table[4];
    int oper_order[4];
    bool checklist[100000];

    //프로그램에서 사용할 전역변수이다. cal_table은 계산이 이루어지는 배열이고, 처음에는 골라진 5개의 수가 들어갈 것이다.(분모가 1인, 즉 자연수의 형태로) oper_table은 5개의 수 사이사이에 들어갈 사칙연산을 저장하는 배열이다. 0은 +, 1은 -, 2는 *, 3은 /를 의미한다. oper_order은 4번의 연산에서 연산순서를 저장하는 배열이다. 24가지 경우가 존재한다. checklist는 5개의 수를 고르는 각 경우에 대해서 만들 수 있는 수(1)와 만들수 없는 수(0)을 기록한다. 처음에는 0으로 초기화된다.

    struct fraction add(fraction a,fraction b){
        fraction x;
        x.d=a.d*b.d;
        x.u=a.u*b.d+a.d*b.u;
        return x;
    }
    struct fraction sub(fraction a,fraction b){
        fraction x;
        x.d=a.d*b.d;
        x.u=a.u*b.d-a.d*b.u;
        return x;
    }
    struct fraction mul(fraction a,fraction b){
        fraction x;
        x.d=a.d*b.d;
        x.u=a.u*b.u;
        return x; 
    }
    struct fraction div(fraction a,fraction b){
        fraction x;
        x.d=a.d*b.u;
        x.u=a.u*b.d;
        if(b.d==0) x.d=0;
        return x; 
    }

    //분수들 사이의 사칙연산을 진행하는 함수이다. 나눗셈 연산의 if(b.d==0) x.d=0;를 눈여겨 봐야 하는데, 이 조건이 추가됨으로써 만약 두 분수중 하나의 분모가 0이라면, 연산 결과의 분모도 항상 0이 되어, 최종 결과에서 분모가 0인지 체크하여 불가능한 연산을 판별할 수 있다. (도중에 0으로 나누었는지)

    int gcd(int a,int b){
        if(a*b==0) return a+b;
        if(a>b) return gcd(a%b,b);
        else return gcd(a,b%a);
    }

    //두 자연수 사이의 최대공약수를 구하는 함수이다. 유클리드 호제법을 이용하였다.

    struct fraction rev(fraction a){
        fraction x;
        int G;
        x.u=a.u>0? a.u:-a.u;
        x.d=a.d>0? a.d:-a.d;
        if(x.d*x.u!=0){
            G=gcd(x.u,x.d);
            x.u/=G;
            x.d/=G;
        }
        if(a.u*a.d<0) x.u=0-x.u;
        return x;
    }

    //어떤 분수를 약분해주는 함수이다. if(a.u*a.d<0) x.u=0-x.u;를 이용하여 음수이면 분자를 음수로 표기하여 그 사실을 알 수 있게 하였다.

    void calculate(int pos){
        int i;
        if(oper_table[pos]==0) cal_table[pos]=(add(cal_table[pos],cal_table[pos+1]));
        if(oper_table[pos]==1) cal_table[pos]=(sub(cal_table[pos],cal_table[pos+1]));
        if(oper_table[pos]==2) cal_table[pos]=(mul(cal_table[pos],cal_table[pos+1]));
        if(oper_table[pos]==3) cal_table[pos]=(div(cal_table[pos],cal_table[pos+1]));
        
        for(i=pos+1; i<4; i++) cal_table[i]=cal_table[i+1];
        for(i=pos; i<3; i++) oper_table[i]=oper_table[i+1];
    }

    //이번에 연산할 연산자의 순서를 입력하면 cal_table 안에서 해당하는 연산자를 실행하여 연산자 양 옆의 두 수를 하나로 묶어준다. 실행한 연산자는 사라진다.

    int main(){
        int number[5],oper[4],i,isBreak,MAX_value=-1,MAX_num[5],announce=0;

    //메인함수가 시작된다. 반복문을 돌리기 위한 number[5],oper[4],i, 반복문을 빠져나오기 위한 isBreak, 최댓값을 저장하기 위한 MAX_value=-1,MAX_num[5], 긴 프로그램 런닝타임 동안 현재 진행도를 알려줄 announce=0을 선언한다.

        for(number[0]=1; number[0]<=9; number[0]++)
        for(number[1]=1; number[1]<=9; number[1]++)
        for(number[2]=1; number[2]<=9; number[2]++)
        for(number[3]=1; number[3]<=9; number[3]++)
        for(number[4]=1; number[4]<=9; number[4]++)
        if(number[0]<=number[1] && number[1]<=number[2] && number[2]<=number[3] && number[3]<=number[4])
        {

    //9개 중 다섯 개의 수를 고르는 모든 경우에 대해서 a<=b<=c<=d<=e인 경우만 고려한다.
            for(i=0; i<100000; i++) checklist[i]=0;
            while(1){
                for(oper[0]=0; oper[0]<4; oper[0]++)
                for(oper[1]=0; oper[1]<4; oper[1]++)
                for(oper[2]=0; oper[2]<4; oper[2]++)
                for(oper[3]=0; oper[3]<4; oper[3]++)
                for(oper_order[0]=0; oper_order[0]<4; oper_order[0]++)
                for(oper_order[1]=0; oper_order[1]<3; oper_order[1]++)
                for(oper_order[2]=0; oper_order[2]<2; oper_order[2]++)
                for(oper_order[3]=0; oper_order[3]<1; oper_order[3]++)

    //연산자와 연산순서로 가능한 모든 경우에 대해서 반복한다.
                {
                    for(i=0; i<5; i++) {
                        cal_table[i].u=number[i];
                        cal_table[i].d=1;
                    }
                    for(i=0; i<4; i++) {
                        oper_table[i]=oper[i];
                    }

    //cal_table과 oper_table에 현재 경우를 복사한다.
                    for(i=0; i<4; i++) calculate(oper_order[i]);
                    cal_table[0]=rev(cal_table[0]);

    //연산을 실행하여 cal_table[0]에 그 결과를 약분된 형태로 저장한다.
                    if(cal_table[0].d==1 && cal_table[0].u>0) checklist[cal_table[0].u]=1;

    //분모가 1이고(정수이고) 분자가 양수이면 해당하는 자연수는 만들 수 있으므로 checklist를 1로 만든다.
                }
                announce++;
                if(announce%100==0) printf("%d/59049 has finished\n",announce);

    //진행도를 표시하는 코드이다.
                
                isBreak=next_permutation(number,number+5);
                if(isBreak==0) break;

    //고른 다섯 가지 수를 나열하는 순열의 경우는 next_permutation이라는 특별한 함수를 사용한다. 이 함수를 호출하면 주어진 배열에서 사전순으로 바로 다음에 있는 순열로 전환해준다. 즉 1,2,3,4,5에서 이 함수를 사용하면 1,2,3,5,4가 되고, 한번 더 호출하면 1,2,4,3,5가 된다. 그리고, 이 함수는 1 또는 0을 반환하는데, 대부분의 경우는 1을 반환하지만, 5,4,3,2,1에서 1,2,3,4,5로 (처음으로) 돌아갈 때만 0을 반환한다. 이를 이용하여 반복문을 탈출할 수 있다.
            }
            
            for(i=0; i<100000; i++) if(checklist[i+1]==0) break;
            if(i>MAX_value){
                MAX_value=i;
                MAX_num[0]=number[0];
                MAX_num[1]=number[1];
                MAX_num[2]=number[2];
                MAX_num[3]=number[3];
                MAX_num[4]=number[4];
            }

    //만들수 있는 1부터 연속한 수의 최댓값을 계산하고 갱신한다.
        }
        
        printf("The Best Case: %d,%d,%d,%d,%d\n Can make number 1~%d",MAX_num[0],MAX_num[1],MAX_num[2],MAX_num[3],MAX_num[4],MAX_value);

    //가능한 최선의 경우를 출력한다.
    }

     

    이 코드를 실행한 결과는 다음과 같다.

    소요시간 71.77초

    4,5,6,7,8을 골랐을 때 1~192의 모든 수를 만들 수 있다!

     

    그렇다면 어떻게 만들 수 있을까?

    위 코드를 수정하자. 전역변수 checklist를 int checklist[194][14]={0,};와 같이 수정한다. 이제 이 체크리스트는 1~193의 각 경우에 대해 만드는 방법을 저장할 것이다. (193에는 저장되지 않을 것이다.)

    메인함수는 다음과 같이 수정한다.

    int main(){
        int number[5]={4,5,6,7,8},oper[4],i,j,k,isBreak,canvas[60],group[5][2],order;

    //고른 숫자 4,5,6,7,8을 number배열에 처음부터 넣어준다. 반복문을 위한 변수 j,k를 추가해주고, oper[]와 oper_order[]의 정보를 수식으로 변환하기 위한 캔버스(그림판) 배열 canvas[60], 괄호로 묶을 위치를 저장하는 group[5][2], 현재 연산순서를 저장하는 order를 선언한다.
        
        while(1){
            for(oper[0]=0; oper[0]<4; oper[0]++)
            for(oper[1]=0; oper[1]<4; oper[1]++)
            for(oper[2]=0; oper[2]<4; oper[2]++)
            for(oper[3]=0; oper[3]<4; oper[3]++)
            for(oper_order[0]=0; oper_order[0]<4; oper_order[0]++)
            for(oper_order[1]=0; oper_order[1]<3; oper_order[1]++)
            for(oper_order[2]=0; oper_order[2]<2; oper_order[2]++)
            for(oper_order[3]=0; oper_order[3]<1; oper_order[3]++)
            {
                for(i=0; i<5; i++) {
                    cal_table[i].u=number[i];
                    cal_table[i].d=1;
                }
                for(i=0; i<4; i++) {
                    oper_table[i]=oper[i];
                }
                for(i=0; i<4; i++) calculate(oper_order[i]);
                cal_table[0]=rev(cal_table[0]);

    //기존과 동일
                if(cal_table[0].d==1 && cal_table[0].u>0 && cal_table[0].u<=193){
                    for(i=0; i<5; i++) checklist[cal_table[0].u][i]=number[i];
                    for(i=5; i<9; i++) checklist[cal_table[0].u][i]=oper[i-5];
                    for(i=9; i<13; i++) checklist[cal_table[0].u][i]=oper_order[i-9];
                }

    //결과값이 1~193 사이이면 해당하는 checklist에 표시해준다.
            }
            isBreak=next_permutation(number,number+5);
            if(isBreak==0) break;
        }

    //기존 코드에서의 반복문이 종료되었다. 이제 checklist에 기록된 정보를 눈으로 볼 수 있는 수식으로 시각화할 것이다.
        
        for(i=1; i<=193; i++){
            for(j=0; j<60; j++) canvas[j]=0;
            for(j=0; j<5; j++) canvas[6*(2*j+1)]=checklist[i][j];
            for(j=0; j<4; j++) canvas[6*(2*j+2)]=-checklist[i][j+5]-1;
            for(j=0; j<5; j++){
                group[j][0]=6*(2*j+1)-1;
                group[j][1]=6*(2*j+1)+1;
            }

    //캔버스를 비워준 뒤, 숫자와 연산자를 넣는다. +는-1, -는-2, *는-3, /는-4로 표시된다, 괄호가 들어갈 자리가 있게 5칸씩의 공백을 남겨준다.
            
            for(j=0; j<4; j++){
                order=checklist[i][j+9];
                canvas[group[order][0]]=-5;
                canvas[group[order+1][1]]=-6;
                group[order][0]--;
                group[order][1]=group[order+1][1]+1;
                for(k=order+1; k<4; k++){
                    group[k][0]=group[k+1][0];
                    group[k][1]=group[k+1][1];
                }
            }

    //연산순서에 맞게 괄호로 수들을 묶어주는 코드이다.
            
            printf("%d = ",i);
            for(j=0; j<60; j++){
                if(canvas[j]>0) printf("%d",canvas[j]);
                if(canvas[j]==-1) printf("+",canvas[j]);
                if(canvas[j]==-2) printf("-",canvas[j]);
                if(canvas[j]==-3) printf("*",canvas[j]);
                if(canvas[j]==-4) printf("/",canvas[j]);
                if(canvas[j]==-5) printf("(",canvas[j]);
                if(canvas[j]==-6) printf(")",canvas[j]);
            }
            printf("\n");

    //캔버스를 앞에서부터 읽으면서 해당하는 문자로 출력해준다.
        }
    }

     

    이 프로그램을 실행하면 4,5,6,7,8로 1~192사이의 수를 어떤 방법으로 만들 수 있는지 출력한다.

    1 = ((8+7)/(6+(5+4)))
    2 = ((8/((7-6)-5))+4)
    3 = ((((8-7)-6)/5)+4)
    4 = (8/(7-(6-(5-4))))
    5 = ((8/(7+(6-5)))+4)
    6 = ((((8*7)-6)/5)-4)
    7 = ((8/(7-6))-(5-4))
    8 = (8/(7/(6+(5-4))))
    9 = ((8/(7-6))+(5-4))
    10 = (8/((7-6)/(5/4)))
    11 = (8+((7/(6-5))-4))
    12 = (((8/(7-6))-5)*4)
    13 = (8+(7-((6+4)/5)))
    14 = (8*((7/(6-5))/4))
    15 = ((8-7)*(6+(5+4)))
    16 = (8*(7-(6-(5-4))))
    17 = ((8/(7-6))+(5+4))
    18 = (8*(7-(6-(5/4))))
    19 = (8+((7/(6-5))+4))
    20 = (8+(7+(6-(5-4))))
    21 = (8+(7+(6/(5-4))))
    22 = (((8*7)-(6*5))-4)
    23 = ((8*(7/(6-4)))-5)
    24 = (8*((7/(6-5))-4))
    25 = (((8+7)*(6-4))-5)
    26 = ((8-7)*((6*5)-4))
    27 = (8-(7-((6*5)-4)))
    28 = ((8/(7-6))+(5*4))
    29 = (8-(7*((6-5)-4)))
    30 = ((8*7)-((6*5)-4))
    31 = (((8-(7-6))*5)-4)
    32 = (8*(7+((6-5)-4)))
    33 = ((8*(7/(6-4)))+5)
    34 = (8*(7-((6+5)/4)))
    35 = (8-((7-(6*5))-4))
    36 = ((8/((7-6)/5))-4)
    37 = ((8/((7-6)/4))+5)
    38 = (8*(((6-7)/4)+5))
    39 = (((8-(7-6))*5)+4)
    40 = (((8*7)-6)/(5/4))
    41 = ((((8*7)-6)-5)-4)
    42 = ((8*7)+(6-(5*4)))
    43 = (8+(7*(6-(5-4))))
    44 = ((8/((7-6)/5))+4)
    45 = (8-(7-((6+5)*4)))
    46 = ((8*7)-((6-4)*5))
    47 = (8+((7*4)+(6+5)))
    48 = (8/((7/6)-(5-4)))
    49 = (((8*7)-6)-(5-4))
    50 = ((8*7)-(6/(5-4)))
    51 = ((8*7)-(6-(5-4)))
    52 = (((8/(7-6))+5)*4)
    53 = ((8*7)+((6-5)-4))
    54 = (8*(7-((6-5)/4)))
    55 = (8-(7-(6*(5+4))))
    56 = ((8+(7-(6-5)))*4)
    57 = (8+(7*(6+(5-4))))
    58 = (8*(7+((6-5)/4)))
    59 = ((8*7)-((6-5)-4))
    60 = ((8*(7/(6-5)))+4)
    61 = ((8*7)+(6-(5-4)))
    62 = ((8*7)+(6/(5-4)))
    63 = ((8*7)+(6+(5-4)))
    64 = ((8+(7+(6-5)))*4)
    65 = ((8+(7-(6-4)))*5)
    66 = (8*(((7+6)/4)+5))
    67 = ((8*(7+(6-4)))-5)
    68 = ((8*(7+(6-5)))+4)
    69 = (8+(((7+6)*5)-4))
    70 = ((8*7)-(6-(5*4)))
    71 = ((8*7)+(6+(5+4)))
    72 = (8/((7-6)/(5+4)))
    73 = ((8*(7+(6/4)))+5)
    74 = (8*(((7*6)-5)/4))
    75 = ((8+7)*(6-(5-4)))
    76 = (8*(7+(5/(6-4))))
    77 = (8+(((7+6)*5)+4))
    78 = (8*(7+((6+5)/4)))
    79 = ((8*(7*(6/4)))-5)
    80 = (8*(7-((6-5)-4)))
    81 = ((((8+7)*6)-5)-4)
    82 = ((8*7)+((6*5)-4))
    83 = (8+((7*(6+4))+5))
    84 = (8*(7/(6/(5+4))))
    85 = ((8*7)+((6*4)+5))
    86 = (((8*(7+5))-6)-4)
    87 = ((8*(7+4))-(6-5))
    88 = (8*((7/(6-5))+4))
    89 = (((8+7)*6)-(5-4))
    90 = ((8*7)+((6*5)+4))
    91 = (((8+7)*6)+(5-4))
    92 = ((8*((7-5)*6))-4)
    93 = (8-((7-(6*4))*5))
    94 = (8*(((7*6)+5)/4))
    95 = (((8*(7+6))-5)-4)
    96 = (8*(7+(6-(5-4))))
    97 = (((8+6)*7)-(5-4))
    98 = ((8*(7+5))+(6-4))
    99 = (((8+7)*6)+(5+4))
    100 = ((8*7)+((6+5)*4))
    101 = (((8+(7+6))*5)-4)
    102 = ((8+7)*(6+(4/5)))
    103 = ((8*(7+6))-(5-4))
    104 = (((8*7)-(6*5))*4)
    105 = ((8*(7+6))+(5-4))
    106 = (8-(7*(6-(5*4))))
    107 = ((8*(7*(6-4)))-5)
    108 = (8*(7+((6/4)+5)))
    109 = (((8+(7+6))*5)+4)
    110 = ((8*7)+(6*(5+4)))
    111 = ((8*6)+(7*(5+4)))
    112 = (8*(7+(6+(5-4))))
    113 = ((8*(7+6))+(5+4))
    114 = (8*(7+(6+(5/4))))
    115 = (((8*(6-4))+7)*5)
    116 = (8*(7+(6*(5/4))))
    117 = ((8*(7*(6-4)))+5)
    118 = (8*((7*(5/4))+6))
    119 = (((8+(7+4))*6)+5)
    120 = ((8-7)*(6*(5*4)))
    121 = (8-(7-(6*(5*4))))
    122 = (((8*7)+5)*(6-4))
    123 = (((8+5)*(6+4))-7)
    124 = ((8*(7+6))+(5*4))
    125 = (8+((7+6)*(5+4)))
    126 = ((8-(7-(5*4)))*6)
    127 = ((8*(6+(5+4)))+7)
    128 = (8*(((7-5)*6)+4))
    129 = (((8+7)*(5+4))-6)
    130 = (8*((7+6)*(5/4)))
    131 = ((8*(7+(6+4)))-5)
    132 = (((7*5)-(8-6))*4)
    133 = (((8+6)*(5+4))+7)
    134 = ((8*(7+(5+4)))+6)
    135 = (8+(7+(6*(5*4))))
    136 = (8*(7+((6-4)*5)))
    137 = (((8+(6+5))*7)+4)
    138 = ((8+((7-4)*5))*6)
    139 = ((8*((7-4)*6))-5)
    140 = ((8*(7+(6+5)))-4)
    141 = ((8*(7+(6+4)))+5)
    142 = (8+((7*(5*4))-6))
    143 = ((((8*5)-6)*4)+7)
    144 = (8*((7+5)*(6/4)))
    145 = (((8+7)*(6+4))-5)
    146 = (8+(((7*4)-5)*6))
    147 = (((8*(6-4))+5)*7)
    148 = ((8*(7+(6+5)))+4)
    149 = ((8*((7-4)*6))+5)
    150 = ((8+7)*((6-4)*5))
    151 = (((8+4)*(7+6))-5)
    152 = (8*((7*(6-4))+5))
    153 = (((8+(6*4))*5)-7)
    154 = (8*(7*((6+5)/4)))
    155 = (((8+7)*(6+4))+5)
    156 = (8+(((7*6)-5)*4))
    157 = ((8*(6*4))-(7*5))
    158 = ((7*((6*5)-8))+4)
    159 = ((((8*6)-7)*4)-5)
    160 = (8/(((7-6)/5)/4))
    161 = (((8+7)*(6+5))-4)
    162 = ((((8-4)*5)+7)*6)
    163 = (8+((7+(6*4))*5))
    164 = (((8+6)*(7+5))-4)
    165 = ((((8*6)-5)*4)-7)
    166 = (((8+(7*5))*4)-6)
    167 = (((8+(6*4))*5)+7)
    168 = (8*(7-(6-(5*4))))
    169 = (((8+7)*(6+5))+4)
    170 = (8+((7+(5*4))*6))
    171 = (8+((7*(6*4))-5))
    172 = (8+(((7*5)+6)*4))
    173 = (((8+5)*(7+6))+4)
    174 = (((8*(7-4))+5)*6)
    175 = (((8+(5*4))*6)+7)
    176 = (8*((7*6)-(5*4)))
    177 = ((((8*5)+6)*4)-7)
    178 = (((8+(7*5))*4)+6)
    179 = ((((8*6)-5)*4)+7)
    180 = ((((8*7)-6)-5)*4)
    181 = (8+((7*(6*4))+5))
    182 = ((8+6)*((5*4)-7))
    183 = ((((8*4)+6)*5)-7)
    184 = (8*(((7-4)*6)+5))
    185 = ((((8*6)-7)-4)*5)
    186 = (((8+(7*4))*5)+6)
    187 = ((((8*4)-6)*7)+5)
    188 = ((8*6)+(7*(5*4)))
    189 = ((8+(7+6))*(5+4))
    190 = (8+(7*((6*5)-4)))
    191 = ((((8*5)+6)*4)+7)
    192 = (8*((7-(6-5))*4))
    193 = ((((+)+)+)+)

    신기한 사실은, 1~192의 모든 수를 나누기 없이 만들 수 있다는 것이다! 궁금하면 직접 코드를 수정해서 해 보시길!

    for(oper[0]=0; oper[0]<4; oper[0]++).. 가 써져 있는 부분에서 4를 3으로 바꾸면 된다! (나누기가 3을 의미하므로)

    결론: 1부터 연속한 자연수를 가장 많이 만들 수 있는 방법은 4,5,6,7,8을 고르는 것이며, 이는 1~192의 모든 수를 만들 수 있다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      muse Lv.1 2018.09.15 13:37

      결국 풀렸네요...

       

      사각형이나 열심히 채워야겠다.

      좋아요0
  •  
    아인수타인 Lv.1 2018.09.16 00:57

    아, 제가 처음부터 문제 이해를 잘못했네요... 아무거나 선택해서 최대로 만드는게 아니구나...

    댓글 작성하기 좋아요0 댓글수0
  •  
    킬러퀸 Lv.4 2018.09.16 17:26

    코딩 열풍이 불어닥친 것 같아요! 문제를 출제한 백진언 연구원 님의 코멘트를 전달할테니 참고하세요!!! laugh

     

    1번 문제

    친구들의 풀이가 모두 의미 있었어요. 친구들의 예상과 달리 1번의 답은 '존재한다'고, 나눗셈을 이용해 정수 뿐만이 아니라 유리수까지 다뤄야 한다는 것이 키 포인트였습니다!

     

    2번 문제

    2번 문제는 컴퓨터의 도움 없이는 해결이 힘든 문제였어요. muse, 누군가, 수돌이 친구가 프로그래밍을 이용해 문제에 접근했는데요, 다들 프로그램을 잘 이용했습니다.

    프로그래밍으로 문제를 풀 때 단점은, 문제 오류가 아닌 프로그램밍 자체를 실수하면 답에 오류가 생길 수 있습니다. 그래서 수학 문제를 프로그래밍으로 해결할 때는 다른 사람이 프로그램을 제대로 구현했는지 확인해서 '엄밀함'을 검증할 수 있습니다. 더 좋은 방법은 다른 방식으로 구현한 프로그램도 똑같은 답을 주는 지를 확인하는 거예요.

    수돌이 친구가 2번 문제를 프로그래밍으로 해결했지만, 수돌이 친구의 코드가 맞는지 다른 사람이 확인하지 않았기 때문에, 다른 친구들이 수돌이 친구의 구현을 검증해서 확인하거나 ②새로 구현을 해서 똑같은 답이 나오는지를 확인하면 문제를 완전히 해결한 걸로 하겠습니다.

    문제를 생각한 친구들 전부 수고 많았고, 아직 할 일이 남았으니 조금만 더 힘내시길 바라요. 감사합니다!

    댓글 작성하기 좋아요0 댓글수0
  •  
    아인수타인 Lv.1 2018.09.16 21:27

    엥? 그럼 아직 완전해결이 아니에요?

    댓글 작성하기 좋아요0 댓글수1
    •  
      킬러퀸 Lv.4 2018.09.21 09:23

      다른 친구들이 검토 or 다른 방법으로 풀 때까지 '잠시만' 기다려 볼게요!!angel

      좋아요0
  •  
    수학자 Lv.1 2018.09.22 19:22

    따로 새롭게 구현하여 보았습니다. 역시 똑같은 답 "192 for (4, 5, 6, 7, 8)"이군요.

    소스 코드: /resources/comment/2018/09/d99406d8b87e238aa15b6f172454a0cc.cpp

    실행 결과(output.txt, 크기 약 31KB): /resources/comment/2018/09/32cd71ab0102d2f22dc991c2bb6d7cc0.txt

    전체 경우를 따져보는 방식을 조금 바꾸어, 확인해야 하는 경우의 수를 조금 줄였습니다. 이 코드에서는 그것이 362,797,056에서 300,231,360으로 줄어든 정도이긴 합니다만, 같은 수가 있는 경우를 더 처리한다면 1.5억(150,000,000) 정도까지, 혹은 더 줄일 수 있을 것 같습니다.

    경우의 수를 줄인 기본적인 아이디어는, 덧셈과 곱셈의 결합법칙이 성립한다는 데서 나왔습니다. 120가지 permutation에 대해 24가지 순서를 해 보는 대신, 5개 중 먼저 연산할 2개를 고르고, 나머지 4개 중 2개를 고르는 식으로 바꾸면, 120*24를 180으로 바꿀 수 있습니다. 대신, 뺄셈과 나눗셈은 연산의 순서를 고려해야 하므로, 연산의 종류가 4가 아닌 6이 됩니다. 5개의 수가 모두 다른 경우 경우의 수가 120*24*4^4=737,280에서 180*6^4=233,280으로 줄어듭니다. 따져봐야 할 경우가 1/3 정도로 줄어든다는 거죠.

     

    ※ 트리비아

    1. (4, 5, 6, 7, 8) 다음으로 좋은 조합은 (2, 4, 7, 8, 9)로, 180까지 나타낼 수 있습니다. 1등(192)과의 격차는 좀 크군요.

    2. 문제의 "1 이상, 9 이하"를 "1 이상 10 이하"로 바꿀 경우 답은 "210 for (2, 3, 7, 9, 10)"입니다. 10을 포함하는 경우 (4, 5, 6, 7, 8)은 전체에서 4등입니다.

    3. (1, 2, 3, 4, 5)로 연속해서 만들 수 있는 수는 75가 한계입니다(541등). 다른 댓글에서 (3, 4, 5, 7, 9)가 있었는데, (3, 4, 5, 7, 9)는 144까지를 만들 수 있는, 1287개 중 39등인 조합입니다.

    4. (1, 1, 1, 1, 1)보다 더 안 좋은 경우가 있을까요? 있습니다! (8, 8, 8, 9, 9)와 (8, 8, 9, 9, 9)가 그 주인공입니다. 이 둘은 5를 나타낼 수 없습니다.

    5. 같은 수 5개를 쓴다면, 1부터 9 중에서는 4가 그나마 낫습니다. (4, 4, 4, 4, 4)는 1부터 21까지의 수를 나타낼 수 있습니다.

    댓글 작성하기 좋아요0 댓글수3
    •  
      킬러퀸 Lv.4 2018.09.27 09:50

      수학자 친구의 풀이 정답입니다!

      좋아요0
    •  
      킬러퀸 Lv.4 2018.09.28 17:07 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      수학자 Lv.1 2018.09.29 12:15 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    누군가 Lv.1 2018.09.23 01:16

    아 늦었네요... 답은 똑같습니다.

    https://scratch.mit.edu/projects/247868405/

    1~9로 만들 수 있는 중복조합리스트를 미리 뽑아놓고 숫자 배열까지 생각하여 계산하였습니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      킬러퀸 Lv.4 2018.09.27 09:50

      누군가 친구의 풀이 정답!!

      좋아요0
  •  
    여백 패르마 Lv.1 2018.09.23 19:48

    해결 됬네요!

    댓글 작성하기 좋아요0 댓글수0
  •  
    아인수타인 Lv.1 2018.09.26 16:54

    근데요, 폴리매스가 원래(매스펀도 그렇고) 중간에 갑툭튀한 분이 정답을 맞히는 경우가 많나요? 보니깐 그런 경우 되게 많던데.

    댓글 작성하기 좋아요0 댓글수2
    •  
      Simon Lv.1 2018.09.26 21:25

      계속 보면서 풀고 게시다가 푼 다음에 올리시는 경우도 있는 것 같고요

      몇몇 분들은 잘하셔서 심심할 때 푸시는 것 같아요.

      갑툭튀하시는 분은 없는 것 같네요.

      좋아요0
    •  
      아인수타인 Lv.1 2018.09.30 20:41

      아니 제 말은 그런 뜻이 아니라 댓글을 안 달다 갑자기 다시는 분 말하는 거예요.

      좋아요0
  •  
    수학장 Lv.1 2018.10.01 21:06

    부럽당.... 나도 멘토링 받아보고 싶당....

    댓글 작성하기 좋아요0 댓글수6
    •  
      아인수타인 Lv.1 2018.10.02 00:06

      ??? 수학장님 수학동아 폴리매스에서 알만한 사람 다 아는 top3(여백 패르마,구머,수학장)로 알고 있었는데, 지금까지 멘토링을 못 받았나요?

      좋아요0
    •  
      수학장 Lv.1 2018.10.02 15:06

      여백 패르마님도 아직 멘토링 안 받아보셨답니다.... 구머님은 받으셨나 문제 플어야 멘토링이 되서 멘토링 받은 분들은 별로 없어요 연락이 안 되서 못 받은 분들도 계시고 수돌이님,c언어님같은 예전 멤버분들이 멤토링 받으신 적 있어요

      좋아요0
    •  
      구머 Lv.1 2018.10.03 22:32

      저도 스케줄 문제땜에 아직 받은 적 없습니다

      좋아요0
    •  
      구머 Lv.1 2018.10.03 23:32

      그리고 이제는 top 3는 아니죠....학교일 바빠서 접은지 거의 4달이 된 것 같은데 ㅜㅜ

      좋아요0
    •  
      수학장 Lv.1 2018.10.08 20:38

      맞아요.... 그리고 제가 1,2번 문제는 가끔 풀어도 메인 문제는 한 번도 푼 적이 없어요ㅠㅠ 제가 무슨 top3입니까

      좋아요0
    •  
      아인수타인 Lv.1 2018.10.09 00:27

      음... 그런가요...(그럼 예전 top3였나...)

      좋아요0
  •  
    구머 Lv.1 2018.10.03 13:19

    오랫만에 놀러왔는데 답들이 코딩밖에 없네요...ㅇㅅㅇ

    댓글 작성하기 좋아요0 댓글수0
  •  
    배고플땐 라면이지 Lv.1 2019.08.04 20:55

    뭐징 왜 이렇게 댓글이 많징

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

  • ☎문의 02-6749-3911