[백준] 숫자 게임

문제보기 - https://www.acmicpc.net/problem/2303

문제명    - 숫자 게임

난이도    - S5

문제유형 - 구현? 완전탐색

풀이일자 - 25.03.21

 

📌 문제 탐색하기

• N명에게 각각 5장의 카드가 주어지고 그 중 3장의 카드의 합의 일의 자리 숫자가 가장 큰 사람이 승리
  • 첫 줄에는 사람의 수를 나타내는 정수 N
    • 2 ≤ N ≤ 1000
  • 그 다음 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어짐
• 게임에서 이긴 사람의 번호를 출력해야 함
  • 이긴 사람이 2명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력

 

🛠 시간복잡도 확인

• 입력 크기
  • 사람 수: N ≤ 1000
  • 한 사람당 5장의 카드 중 3장을 선택하는 경우의 수: 5x4/2x1 = 10
• O(N*10)으로 완전 탐색 가능!

 

📌 코드 설계하기

1. 입력 처리
   • 참가자 수 N 을 입력받기
   • 각 참가자의 5장의 카드 숫자 입력받기
2. 조합을 활용한 최대값 계산
   • 5장 중 3장을 선택하는 모든 조합을 생성
     • itertools.combinations()를 사용 
   • 합의 일의 자리 값중 최대값을 저장
     • sum % 10
3. 결과 출력
   • 최대값을 가진 참가자 출력
   • 동점이면 참가자 번호가 큰 사람 출력

 

📌 정답 코드(1회차)

import sys
import itertools

# 조합을 활용한 최대값 계산
def find_winner(N, cards):
    max_value = 0  # 가장 큰 일의 자리 값
    winner = 0  # 우승자 번호
    
    for i in range(N):
        best_value = 0  # 현재 참가자의 최댓값
        
        # 5장 중 3장을 선택하는 모든 조합을 생성
        for comb in itertools.combinations(cards[i], 3):
            value = sum(comb) % 10  # 일의 자리 값 계산
            best_value = max(best_value, value)
        
        # 최대값을 가진 참가자 출력 , 동점이면 참가자 번호가 큰 사람 출력
        if best_value > max_value or (best_value == max_value and i + 1 > winner):
            max_value = best_value
            winner = i + 1  # 1번부터 시작하므로 인덱스+1
    
    return winner

# 입력 처리
N = int(sys.stdin.readline().strip())  # 참가자 수
cards = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 각 참가자의 5장의 카드 숫자 입력받기

# 결과 출력
print(find_winner(N, cards))