[백준 2303번] 숫자 게임 - python

https://www.acmicpc.net/problem/2303

📌 문제 탐색하기

목표

• 각각 1~10사이의 수가 적힌 다섯 장의 카드 중 세 장의 카드에 적힌 수의 합을 구한 후 일의 자리 수가 가장 큰 사람이 이기는 게임을 진행한다.
• n명에게 각각 다섯 장의 카드가 주어졌을 때 이기는 사람을 출력한다.

입력값

• 첫 줄에는 사람의 수 n이 주어진다. (2 ≤ n ≤ 1000)
• n줄에 걸쳐 각 사람이 가진 카드가 주어진다. 이는 1 ~ 10의 정수 다섯 개이다.
• ex)
• 3 7 5 5 4 9 1 1 1 1 1 2 3 3 2 10

출력값

• n명에게 각각 다섯 장의 카드가 주어지고 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 출력한다.
• 가장 큰 수를 갖는 사람이 두 명 이상일 경우는 번호가 가장 큰 사람의 번호를 출력한다.
• ex)
• 1

📌 코드 설계하기

해결 아이디어

• 각 배열마다 3중 for문을 돌면 너무 시간 복잡도가 커지는 문제가 있다. 이를 어떻게 해결하지..?
• 온전히 계산이 들어가야하는 문제이기 때문에 덧셈 혹은 뺄셈이 가능한 방법이다. 이중 뺄셈을 택해서 이중 for문을 돌아 두 개의 값을 제거하도록 하자.

📌 정답 코드

import sys

n = int(sys.stdin.readline().strip())
sum_1 = [0]
for i in range (n):
    arr = list(map(int, sys.stdin.readline().split()))
    sums = sum(arr)
    max_ = (sums - (arr[0] + arr[1])) % 10
    for i in range(4):
        for j in range(i+1, 5):
            if (sums - arr[i] - arr[j])% 10 > max_:
                max_ = (sums - arr[i] - arr[j])% 10
    sum_1.append(max_)

max_num = max(sum_1)
for i in range (len(sum_1)-1, 0, -1):
    if sum_1[i] == max_num:
        print(i)
        exit()

print(sum_1.index(max_num))

전체 연산 횟수

• 1000이라고 가정하고 구해보자.
• sum 5번 + 이중 for문 50번 → 한 번 계산 할 때 55번 연산
• 따라서 55,000번 연산
• 그 이후 답을 구하는 과정도 max 1000번, for문 1000번, index 1000번이므로 3000번이다.
• 총합은 대략 58000번 연산으로 2초 내로 충분히 들어올 수 있다.