코드잼 C도 풀었습니다. (댓글 스포)

  • Andromeda
    Andromeda

    어제 새벽까지 코딩해서 "맞았습니다!"보고 잤어요.
    우와, 신난다.


    8년 전
8개의 댓글이 있습니다.
  • JongMan
    JongMan

    우와 축하염 ^^


    8년 전 link
  • hyunhwan
    hyunhwan

    으엉 스포좀 날려주세요. 어떻게 푸셨는지 궁금합니다.


    8년 전 link
  • unbing
    unbing

    i = 1일 때 맞추기 위해서는 이 아이가 B개의 검은 모자를 보거나 W개의 흰 모자를 보아야 합니다.
    i = 2일 때 맞추기 위해서는 이 아이가 B - 1 개의 검은 모자를 보거나 W - 1개의 흰 모자를 보아야 합니다. + 이 아이의 모자가 더해졌을 때 검은 모자가 B개가 되거나 흰 모자가 W개가 되면 안됩니다. (이러면 i = 1이 답이 되버리죠.)
    ...
    i = x일 때는 어떤 경우를 세어보아야 할지 고민하시면 될 것 같습니다. :)
    답이 맞다고 입증하기 위해서는 induction을 약간 변형해 보면 되죠.

    코드를 생각해 보자면 i번 아이가 맞추었을 때, 그 앞의 모자 중 b개가 검은색이고, w개가 흰색이라고 먼저 정합니다 (b와 w가 위의 조건을 만족하게끔). (b + w) choose w개의 가짓수가 있죠. 그러면 i부터 감소하면서 이 아이의 모자의 갯수를 정해줍니다 (다른 아이들이 못 맞춘다는 조건을 만족하면서). 언뜻보면 2^i개의 선택을 해 보아야 할 것 같지만 각각의 i에 대하여 (b, w)만 중요하기 때문에 적은 경우의 수만 memorization을 이용해서 확인해 보면 됩니다. :)


    8년 전 link
  • Andromeda
    Andromeda

    .


    8년 전 link
  • Andromeda
    Andromeda

    풀이 과정은 unbing님이 말씀하신 것과 비슷합니다. 다만 1st부터 (i-1)th의 아이에게 모자를 씌우는 방법의 수를 구할 때, 남은 모자의 개수를 생각해서 조합으로 구했습니다.


    8년 전 link
  • iddaga
    iddaga

    Link 하면 바로 뒤에 달리려나 ㅎㅎ i 번 아이가 처음 맞췄다면 1~(i-1) 번 아이들은 아무 모자나 써도 되용 2^(i-1)


    8년 전 link
  • iddaga
    iddaga

    그냥 코멘트 주소를 얻는거구나


    8년 전 link
  • JongMan
    JongMan

    1 낚이심


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.