1번 방법: combination함수
우선 상당히 복잡하게 푼 방법부터 보이자면 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
from itertools import combinations
N, M = map(int, input().split())
num = list(map(int, input().split()))
sums = []
ans = [0]
subPrev = 9999999
# print(list(combinations(num, 3)))
combis = list(combinations(num, 3))
for i in range(len(combis)):
sums.append(sum(combis[i]))
# print(sums)
if sums[i] <= M:
sub = abs(M - sums[i])
if subPrev >= sub:
subPrev = sub
ans.pop()
ans.append(sums[i])
# print(ans)
else:
pass
print(ans[0])
|
cs |
from itertools import combinations 라는 코드를 먼저 아는 것이 중요하다.
combinations 즉, 조합을 알아서 찾아주는 모듈이라고 보면 된다.
사용 방법은 combis = list(combinations(num, 3)) 처럼 조합들을 넣고 싶은 변수 list 형태로 num의 리스트를 몇 개씩(이 코드에서는 3개씩) 조합하여 결과를 만들어내는 것이다.
따라서, 위의 방법으로 조합을 먼저 생성해내고,
조합의 갯수만큼 for문을 돌면서,
각 조합에 대한 합을 sums라는 리스트에 append시킨다.
그러면서 문제의 조건인 "합이 M을 넘어서는 안된다" 라는 조건은 if문에 주고,
조건이 부합하면, M과 합의 차를 절댓값으로 구함으로써, 그 차이가 가장 작은 수 (=M과 가장 가까운 수)를 구한다.
(이때, "M을 넘지 않는다" 라는 조건은 M을 포함하여 넘지 않는다고 해석해서 if sums[i] <= M: 로 처리해야한다.... 이 부분 때문에 몇 번이나 틀렸다...)
2번 방법: 3중 for문
아래와 같은 코드로 짜면 시간도 훨씬 짧게 들이면서 간단하게 풀 수 있게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
n, m = map(int, input().split())
num = list(map(int, input().split()))
l = len(num)
ans = 0
for i in range(0, l-2):
for j in range(i+1, l-1):
for k in range(j+1, l):
if(num[i] + num[j] + num[k] > m):
continue
else:
ans = max(ans ,num[i] + num[j] + num[k])
print(ans)
|
cs |
인터넷 검색을 하면서 3중 for문을 통해서 구할 수 있게 된다는 것을 알게 되었다...
브루트포스(bruteforce)의 알고리즘 사용으로써, 모든 경우의 수를 구한 것이다.
코딩테스트를 보게 되면 1분 1초가 소중하기 때무에 이런 형태로 최대한 빠르게 풀 수 있는 코드를 계속 보고 익혀두는 것이 좋을 듯 하다.
문제 출처: https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
'코딩 문제풀이 및 연습 > Python 연습' 카테고리의 다른 글
| [백준] 13305_주유소 파이썬 (그리디 알고리즘) (0) | 2021.10.07 |
|---|---|
| [백준] 7568_덩치 파이썬 (0) | 2021.09.27 |
| [백준] 5532_방학 숙제 파이썬 (if-else vs ceil함수) (0) | 2021.09.22 |
| [백준] 2953_나는 요리사다. (0) | 2021.09.21 |
| [백준] 2292_벌집 파이썬 (0) | 2021.09.19 |