https://www.acmicpc.net/problem/2798
문제
ㅋㅈㄴ에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 ㅋㅈㄴ마다 다양한 규정이 있다.
(2/21 ㅋㅈㄴ 검열 이유: 원문으로 적으면 velog 오류로 포스트가 자동으로 비공개 됨)
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
입력
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.
예제 입출력
풀이 1 (정답)
N, M = map(int, input().split())
cards = list(map(int, input().split()))
sum, sum_max = 0, 0
for i in range(0, N-2):
for j in range(i+1, N-1):
for k in range(j+1, N):
sum = cards[i] + cards[j] + cards[k]
if sum > sum_max and sum <= M:
sum_max = sum
print(sum_max)브루트 포스로 풀었다.
특별히 좋은 생각이 떠오르지 않아서,
그냥 for문 세 개 쓰고 range를 적절히 정해주기로 했다.
난 수학 못하는 바보라서 그런지 range의 시작과 끝 인덱스를 정하는게 매번 어렵다.
그래서 예시를 들어서 생각해본다.
N = 5일 때 나올 수 있는 i, j, k를 전부 나열해본다면,
0,1,2
0,1,3
0,1,4
0,2,3
0,2,4
0,3,4
1,2,3
1,2,4
1,3,4
2,3,4
-> i는 0~N-2, j는 i+1~N-1, k는 j+1~N의 범위를 가진다.다만 코드가 너무 지저분한데...
풀이 2 (정답)
N, M = map(int, input().split())
card = list(map(int, input().split()))
result = 0
for i in range(0, N):
for j in range(i+1, N):
for k in range(j+1, N):
sum = card[i] + card[j] + card[k]
if sum <= M:
result = max(result, sum)
print(result)풀이 1의 코드를 다듬었다.
놀랍게도 range의 끝 인덱스를 N으로만 정해줘도 됐다.
예를 들어 N = 5라면,
i = 3일 때, j의 range는 (4, 5), k의 range는 (5, 5)가 되므로,
세 번째 for문은 실행되지 않게 되기 때문이다.
또한 sum_max 변수를 이용해 부등식을 두 번 사용하는 대신
result = max(result, sum)으로 최대합을 갱신하였다.
다만 max 함수를 사용해서인지 실행 시간은 28ms 증가하였다.
또한 합을 구하는 과정에서 sum을 변수명으로 사용하였는데, 좋지 않은 것 같다.
앞으로는 자제하도록 하겠다.
풀이 3 (참고한 풀이)
from itertools import combinations
N, M = map(int, input().split())
card = list(map(int, input().split()))
ans = 0
for i in combinations(card, 3):
if ans < sum(i) <= M:
ans = sum(i)
print(ans)먹구름의 하늘님의 코드를 참고하였다.
문제를 보고 조합과 관련된 라이브러리가 있다면 좋겠다고 생각했는데,
itertools가 그것이었다.
from itertools import combinations, permutations
# combinations: 조합, permutations: 순열
print(permutations(range(3), 2))
print(list(permutations(range(3), 2)))
print(combinations(range(3), 2))
print(list(combinations(range(3), 2)))
# 실행 결과
<itertools.permutations object at 0x104518810>
[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]
<itertools.combinations object at 0x104518810>
[(0, 1), (0, 2), (1, 2)]파이썬 내장 라이브러리인 itertools는 특정 배열에 대하여 순열이나 조합을 이용한 문제를 풀 때 유용하며, 자신의 반복자를 만드는 모듈이라고 한다.
itertools에 관한 자세한 설명은 이곳을 참고하자.
오늘의 교훈
- for문에서 range의 시작, 끝 인덱스를 신중히 지정하자.
- 변수명으로 sum을 사용하지 말자.
- 순열, 조합 관련 문제에서는 itertools 라이브러리를 이용해보자.
