📌 구해야 하는 정답

N명의 사람들이 모여 숫자 게임을 합니다.

각 사람에게는 1~10까지의 수가 적힌 다섯 장의 카드가 주어집니다.

각 사람들은 이 중 세 장의 카드를 골라 합을 구한 후 일의자리 수를 구합니다.

각 사람든 세장의 카드를 선택할 때 일의 자리 수가 가장 크게 되도록 카드를 선택합니다.

이 때 이 값이 가장 큰 사람이 이기게 됩니다.

각 사람이 받은 카드가 입력으로 주어질 때 이긴 사람의 번호를 찾는 문제입니다.

이긴 사람이 두명 이상일 경우에는 번호가 가장 큰 사람이 정답입니다

📌 풀이 하기

1️⃣ 풀이 방법 고민하기

한 사람이 만들 수 있는 가장 큰 일의 자리 수를 구하는데는 어떤 연산이 필요할까요?

5장의 카드 중 3장의 카드를 고르는데에는 543의 조합이 존재합니다.

따라서 한 사람에 대해 총 60번의 연산을 거쳐야 그사람이 만들 수 있는 가장 큰 일의 자리 수를 구할 수 있습니다.

이 때 문제에서 N명의 사람이 주어집니다.

즉, N개의 사람들에 대해 각각 만들 수 있는 가장 큰 일의 자리 숫자를 구해야 하므로,

총 N*60, 최대 60,000번의 연산이 소요 됩니다.

이후 N명의 사람 중 가장 큰 수를 가지고 있는 사람을 탐색하기 위해 추가로 O(N)의 시간복잡도가 소요됩니다.