📃문제
N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경우 (7, 4, 9)를 선택하면 합이 20이 되어 일의 자리 수는 0이 되고, (5, 5, 9)를 선택하면 합이 19가 되어 일의 자리 수는 9가 된다. 게임을 이기기 위해서는 세 장의 카드를 선택할 때 그 합의 일의 자리 수가 가장 크게 되도록 선택하여야 한다.
예를 들어, N=3일 때
1번 사람이 (7, 5, 5, 4, 9),
2번 사람이 (1, 1, 1, 1, 1),
3번 사람이 (2, 3, 3, 2, 10)의
카드들을 받았을 경우, 세 수의 합에서 일의 자리 수가 가장 크게 되도록 세 수를 선택하면
1번 사람은 (5, 5, 9)에서 9,
2번 사람은 (1, 1, 1)에서 3,
3번 사람은 (2, 3, 3)에서 8의
결과를 각각 얻을 수 있으므로 첫 번째 사람이 이 게임을 이기게 된다.
N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.
📃입력
첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다.
📃출력
게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.
📃예제 입력 1
3
7 5 5 4 9
1 1 1 1 1
2 3 3 2 10
📃예제 출력 1
1
✏️문제 탐색하기
각 사람이 가진 다섯 장의 카드 중 세 장을 선택해 합의 일의 자리 수를 계산하고 가장 큰 값을 가지는 사람을 찾아야 하는 문제.
주어진 조건:
- 1부터 10사이의 정수가 다섯 개씩 주어짐.
- 이긴 사람이 두 명 이상일 경우 번호가 가장 큰 사람의 번호를 출력.
✏️알고리즘 선택
전체 시간 복잡도는 O(N) 로 효율적으로 동작합니다
✏️코드 설계하기
- 첫 줄에서 사람 수 N 을 읽어옵니다.
- 각 사람의 카드 정보를 리스트로 입력받습니다.
- 3중 루프를 통해 다섯 장 중 세 장의 조합을 생성합니다.
- 각 조합의 합을 계산하고, 그 합의 일의 자리 수를 구합니다.
- 계산된 값 중 최댓값을 max_remainder로 갱신합니다.
- list_에 저장된 각 사람의 최댓값 중에서, 역순 탐색으로 가장 큰 값의 마지막 위치를 찾습니다.
- 문제 요구사항에 따라 번호는 1부터 시작하므로 결과에 +1을 더합니다.
✏️시도 회차 수정 사항
1회차
이긴 사람이 두 명 이상일 수 있다는 것을 생각하지 못함.. 그래서 2회차로 구현
import sys
N = int(sys.stdin.readline())
list_ = []
for _ in range(N):
count = 0
card_list = list(map(int, sys.stdin.readline().split()))
for i in range(5):
for j in range(i + 1, 5):
for k in range(j + 1, 5):
num = (card_list[i] + card_list[j] + card_list[k]) % 10
if num >= count:
count = num
list_.append(count)
list_.sort(reverse=True)
print(list_.index(list_[0])+1)2회차
두 명일 수 있다는 것을 대비해서 구현했는데 이게 왠걸 번호가 가장 큰 사람의 번호를 출력이란다..
그래서 for문을 거꾸로 실행시켜야 된다는 것을 깨달아 다시 수정.....
import sys
N = int(sys.stdin.readline())
list_ = []
for _ in range(N):
count = 0
card_list = list(map(int, sys.stdin.readline().split()))
for i in range(5):
for j in range(i + 1, 5):
for k in range(j + 1, 5):
num = (card_list[i] + card_list[j] + card_list[k]) % 10
if num >= count:
count = num
list_.append(count)
for i in range(len(list_)):
if list_[i] == max(list_):
print(i + 1)
break✏️코드 구현
import sys
N = int(sys.stdin.readline())
list_ = []
for _ in range(N):
count = 0
card_list = list(map(int, sys.stdin.readline().split()))
for i in range(5):
for j in range(i + 1, 5):
for k in range(j + 1, 5):
num = (card_list[i] + card_list[j] + card_list[k]) % 10
if num >= count:
count = num
list_.append(count)
for i in range(len(list_)-1, -1, -1):
if list_[i] == max(list_):
print(i + 1)
break