코딩 테스트
문제 16 : 야찌(Yahtzee)
쁜사
2025. 4. 18. 14:12
야찌 게임은 다섯 개의 주사위를 써서 하는 게임으로, 13 라운드에 걸쳐서 주사위를 던지는 게임이다. 스코어 카드에는 13개의 카테고리가 있다. 각 라운드에서는 게임 참가자가 선택한 카테고리에 의해 점수를 딸 수 있는데, 이때 각 카테고리는 한 게임에 한 번만 쓸 수 있다. 13개의 카테고리에서는 다음과 같은 식으로 점수를 딴다.
- 1 - 모든 1들의 합
- 2 - 모든 2들의 합
- 3 - 모든 3들의 합
- 4 - 모든 4들의 합
- 5 - 모든 5들의 합
- 6 - 모든 6들의 합
- 찬스 - 모든 숫자의 합
- 같은 숫자 세 개 - 적어도 세 개가 같은 숫자일 때, 모든 숫자의 합
- 같은 숫자 네 개 - 적어도 네 개가 같은 숫자일 때, 모든 숫자의 합
- 같은 숫자 다섯 개 - 적어도 다섯 개가 같은 숫자일 때, 50점
- 쇼트 스트레이트 - 네 개가 연속된 숫자일 때(1, 2, 3, 4 또는 2, 3, 4, 5 또는 3, 4, 5, 6), 25점
- 롱 스트레이트 - 다섯 개가 연속된 숫자일 때(1, 2, 3, 4, 5 또는 2, 3, 4, 5, 6), 35점
- 풀 하우스 - 세 개가 같은 숫자이고 나머지 두 개가 같은 숫자일 때(예를 들면 2, 2, 5, 5, 5), 40점
마지막 여섯 개의 카테고리는 조건이 만족되지 않으면 0점으로 처리한다.
이 게임의 총점은 13개의 카테고리 각각의 점수를 모두 더한 점수며 첫번째부터 여섯 번째까지의 카테고리 총합이 63점 이상이면 보너스 점수 35점이 추가된다.
여러 라운드가 주어졌을 때 가능한 최고 점수를 계산하라.
입력
각 줄에는 1이상 6 이하의 정수가 다섯 개 있으며 이는 각 라운드에 나온 주사위 다섯개의 숫자를 나타낸다. 매 게임마다 13줄이 입력되며 입력 데이터에 들어있는 게임 횟수에는 제한이 없다.
출력
한 줄에 15개의 숫자를 출력한다. 15개의 숫자는 각 카테고리별 점수(위에 나와 잇는 순서대로)와 보너스 점수(0 또는 35), 그리고 총점이다. 여러 방식으로 카테고리를 적용했을 때 같은 점수가 나오면 그 중 아무 결과나 출력해도 된다.
예제
아래처럼 입력에 대한 출력이 나온다.
해설
해가 지나도록 질질 끌었던 문제다. 룰 적용에 대한 모든 조합을 구하고, 각 조합에 대한 점수를 계산해서 최고 점수를 찾는 것이다. 다만 전체 조합의 수가 13! 이기 때문에 시간이 어마어마하게 걸린다. 이에 대한 해답으로 0점인 룰은 제외해서 조합의 수를 줄이니 어찌어찌 수 분만에 풀이가 가능했다.
'같은 숫자 세 개'와 '같은 숫자 네 개' 룰의 점수 계산이 헷갈릴 수 있다. 조건이 맞을 때, 숫자 5개의 점수를 모두 더하는 것이다. 처음에는 3개, 4개만 더했더니 자꾸 답이 틀렸는데, 이 부분을 유의하면 좋을 것 같다.
# Quiz 0016, Yahtzee
# written by badsaram
import sys
class Yahtzee(object):
def __init__(self):
self.dice_try = []
self.dice_try_score = []
self.combination = [0] * 13
self.combination_count = 0
self.max_try_count = 13
self.max_pattern_count = 13
self.max_combination_count = 0
self.max_score = 0
self.max_score_combination = [0] * 13
def input(self):
for i in range(0, self.max_try_count):
str = input()
tokens = str.split(' ')
if (len(tokens) > 5):
print("wrong input number.")
sys.exit(-1)
int_tokens = []
for token in tokens:
if (int(token) > 6):
print("wrong input number.")
sys.exit(-1)
int_tokens.append(int(token))
self.dice_try.append(int_tokens)
def test_input1(self):
for i in range(0, self.max_try_count):
self.dice_try.append([1, 2, 3, 4, 5])
def test_input2(self):
self.dice_try.append([1, 1, 1, 1, 1])
self.dice_try.append([6, 6, 6, 6, 6])
self.dice_try.append([6, 6, 6, 1, 1])
self.dice_try.append([1, 1, 1, 2, 2])
self.dice_try.append([1, 1, 1, 2, 3])
self.dice_try.append([1, 2, 3, 4, 5])
self.dice_try.append([1, 2, 3, 4, 6])
self.dice_try.append([6, 1, 2, 6, 6])
self.dice_try.append([1, 4, 5, 5, 5])
self.dice_try.append([5, 5, 5, 5, 6])
self.dice_try.append([4, 4, 4, 5, 6])
self.dice_try.append([3, 1, 3, 6, 3])
self.dice_try.append([2, 2, 2, 4, 6])
def calc(self):
for i in range(0, len(self.dice_try)):
self.calc_pattern(self.dice_try[i])
# brutal force
self.traverse(0)
# fill empty item
for i in range(0, len(self.max_score_combination)):
if (self.max_score_combination[i] == 0):
for j in range(1, self.max_pattern_count + 1):
if (j in self.max_score_combination):
pass
else:
self.max_score_combination[i] = j
break
# print answer
#print(self.max_score_combination)
answer = [0] * 15
for i in range(0, len(self.max_score_combination)):
pattern = self.max_score_combination[i]
score = self.dice_try_score[i][pattern]
answer[pattern - 1] = score
if (sum(answer[0:6]) >= 63):
answer[13] = 35
answer[14] = self.max_score
print(answer)
def calc_pattern(self, dices):
switch = {
1 : self.calc_pattern_1(dices),
2 : self.calc_pattern_2(dices),
3 : self.calc_pattern_3(dices),
4 : self.calc_pattern_4(dices),
5 : self.calc_pattern_5(dices),
6 : self.calc_pattern_6(dices),
7 : self.calc_pattern_7(dices),
8 : self.calc_pattern_8(dices),
9 : self.calc_pattern_9(dices),
10 : self.calc_pattern_10(dices),
11 : self.calc_pattern_11(dices),
12 : self.calc_pattern_12(dices),
13 : self.calc_pattern_13(dices)
}
item = []
item.append(dices)
for i in range(1, 14):
item.append(switch.get(i))
self.dice_try_score.append(item)
def calc_pattern_1(self, dices):
return dices.count(1) * 1
def calc_pattern_2(self, dices):
return dices.count(2) * 2
def calc_pattern_3(self, dices):
return dices.count(3) * 3
def calc_pattern_4(self, dices):
return dices.count(4) * 4
def calc_pattern_5(self, dices):
return dices.count(5) * 5
def calc_pattern_6(self, dices):
return dices.count(6) * 6
def calc_pattern_7(self, dices):
return sum(dices)
def calc_pattern_8(self, dices):
for i in range(1, 7):
if (dices.count(i) >= 3):
return sum(dices)
return 0
def calc_pattern_9(self, dices):
for i in range(1, 7):
if (dices.count(i) >= 4):
return sum(dices)
return 0
def calc_pattern_10(self, dices):
sum = 0
for i in range(1, 7):
if (dices.count(i) >= 5):
sum = 50
break
return sum
def calc_pattern_11(self, dices):
sum = 0
if (1 in dices) and (2 in dices) and (3 in dices) and (4 in dices):
sum = 25
if (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices):
sum = 25
if (3 in dices) and (4 in dices) and (5 in dices) and (6 in dices):
sum = 25
return sum
def calc_pattern_12(self, dices):
sum = 35
if (1 in dices) and (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices):
sum = 35
if (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices) and (6 in dices):
sum = 35
return sum
def calc_pattern_13(self, dices):
sum = 0
meet2 = False
meet3 = False
for i in range(1, 7):
if (dices.count(i) == 2):
meet2 = True
elif (dices.count(i) == 3):
meet3 = True
if ((meet2 == True) and (meet3 == True)):
sum = 40
return sum
def calc_combination(self, combination):
total_score = 0
pattern_1_6_score = 0
for i in range (0, self.max_try_count):
pattern = combination[i]
if (pattern != 0):
total_score = total_score + self.dice_try_score[i][pattern]
if (pattern in range(1, 7)): # 1
pattern_1_6_score = pattern_1_6_score + self.dice_try_score[i][pattern]
if (pattern_1_6_score >= 63):
total_score = total_score + 35 # if score of pattern 1˜6 is greater than 63, bonus 35 is added
if (total_score > self.max_score):
self.max_score = total_score
self.max_score_combination[:] = combination
return total_score
def count_combination_length(self, combination):
return len(list(filter(lambda x: x != 0, combination)))
def traverse(self, depth):
if (depth >= self.max_try_count): # depth >= 13
return
for i in range(1, self.max_try_count + 1):
if (i in self.combination):
continue
if (self.dice_try_score[depth][i] == 0):
continue
self.combination[depth] = i
if (depth == (self.max_try_count - 1)): # depth == 12
total_score = self.calc_combination(self.combination)
self.max_combination_count = self.max_try_count # 13
self.combination_count = self.combination_count + 1
#print("%10d | %s | %d" % (self.combination_count, self.combination, total_score))
self.traverse(depth + 1)
self.combination[depth] = 0
combination_len = self.count_combination_length(self.combination)
if (combination_len >= self.max_combination_count):
total_score = self.calc_combination(self.combination)
self.max_combination_count = combination_len
self.combination_count = self.combination_count + 1
#print("%10d | %s | %d" % (self.combination_count, self.combination, total_score))
if __name__ == '__main__':
obj = Yahtzee()
obj.input()
#obj.test_input1()
#obj.test_input2()
obj.calc()