본문 바로가기

책 정리/Programming Challenges : 알고리즘 트래이닝 북

문제 16, 야찌(Yahtzee)

이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • firefox4 b8
  • eclipse + vrapper
  • lua 5.1.4

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 16 Yahtzee, page 82 ~ 83)

참고 링크

내용

이 문제의 목표는 야찌 게임에서 최고 점수를 찾는것이다.

야찌(Yahtzee) 게임은 어떻게 하는 것인가?

  1. 주사위 5개를 준비 한다.
  2. 5개의 주사위를 모두 던지고, 각 주사위의 눈을 기록한다. 이것을 13번 반복한다.
  3. 적어 놓은 13개의 기록을 카테고리와 대조하여 점수를 낸다.
  4. 한번 대조된 주사위 기록은 쓸수 없다.

  5. 이렇게 모두 모운 점수를 총점이라고 하고, 총점이 높은 사람이 이기는 게임이다.

점수 계산 카테고리들

  1. 카테고리 1 - 모든 1들의 합
  2. 카테고리 2 - 모든 2들의 합
  3. 카테고리 3 - 모든 3들의 합
  4. 카테고리 4 - 모든 4들의 합
  5. 카테고리 5 - 모든 5들의 합
  6. 카테고리 6 - 모든 6들의 합

  7. 카테고리 7 - 모든 숫자의 합
  8. 카테고리 8 - 같은 주사위가 적어도 3개 일 때, 모든 숫자의 합
  9. 카테고리 9 - 같은 주사위가 적어도 4개 일 때, 모든 숫자의 합

  10. 카테고리 10 - 같은 주사위가 적어도 5개 일 때, 50점
  11. 카테고리 11 - 4 개의 주사위가 연속된 숫자일 때, 25점
  12. 카테고리 12 - 5 개의 주사위가 연속된 숫자일 때, 35점

  13. 카테고리 13 - 3개가 같은 숫자이고, 나머지 2개가 같은 숫자일때, 40점
  14. 카테고리 14 - 카테고리 1 ~ 6까지의 합이 63점 이상일 경우, 35점
맛보기 문제 풀이




여담

  • 백트랙킹 알고리즘(backtracking:모든 경우의 수로 문제는 푸는 알고리즘) 이란 이름을 알았다.
    - 전부 백트랙킹으로 풀기엔 시간이 너무 많이 들어서, 카테고리 1 ~ 6 까지만 백트랙킹을 이용했다.

  • 휴리스틱 알고리즘(heuristic:경험이나 학습으로 문제를 푸는 알고리즘) 이란 이름을 알았다.
    - 카테고리 7 ~ 13 까지는 휴리스틱 알고리즘을 사용했는데, 썩 좋은 답을 내놓지 못했다.(최고점보다 2점이나 낮다...)

  • 메모라이즈(memorize) 기법 이란 이름을 알았다.
    - 계속 계산할 필요 없이, 한번 계산한 것을 기록해 두었다가 쓰는 기법인데, 여기선 모든 스코어를 기록해 두었다가 사용했다.

  • 1년 전에 이 문제를 접했다가 못풀어서, 쉬었었는데, 얼마전에 시작해서, 감잡고 다시 풀었다.

:wq