다음과 같이 코드를 만들면 된다.

1
2
3
4
5
6
7
8
9
from itertools import combinations
num =  int(input())
nums = []
for i in range(1, num):
    nums.append(i)
# print(nums)
combis = list(combinations(nums, 3))
# print(combis)
print(len(combis))
 cs

 

 

이전에 https://gettingtoknowit.tistory.com/129?category=919340 에서 combination 함수를 사용했던 적이 있다.

 

[백준] 2798_블랙잭 파이썬 (combination함수 vs 3중for문)

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,..

gettingtoknowit.tistory.com

똑같이 이번 문제에서도 사용하면 된다.

 

그리고 중요한 부분은 언제나 그렇듯 "입력값"을 제대로 아는 것이다.

입력값을 보면 "The input will be the positive integer J (1 ≤ J ≤ 99), which is the jersey number of the goal scorer."라고 되어있다.

즉, goal scorer의 번호를 입력하기 때문에, 4명 중 마지막 4번째 사람의 번호를 입력한다는 뜻이고, 

문제의 조건에 따라 마지막 1명은 항상 고정된 숫자로 만든다면,결국 조합은 3명의 조합의 갯수만 구하면 된다! (그래서 7행을 보면 3만 뽑아서 쓴다)

 

 

문제 출처: https://www.acmicpc.net/problem/6768

 

6768번: Don’t pass me the ball!

A CCC soccer game operates under slightly different soccer rules. A goal is only counted if the 4 players, in order, who touched the ball prior to the goal have jersey numbers that are in strictly increasing numeric order with the highest number being the

www.acmicpc.net

저작자표시 비영리 변경금지

'코딩 문제풀이 및 연습 > Python 연습' 카테고리의 다른 글

[백준] 11399_ATM 파이썬 (그리디 알고리즘 / 정렬)  (0) 2021.10.07
[백준] 13305_주유소 파이썬 (그리디 알고리즘)  (0) 2021.10.07
[백준] 7568_덩치 파이썬  (0) 2021.09.27
[백준] 2798_블랙잭 파이썬 (combination함수 vs 3중for문)  (0) 2021.09.26
[백준] 5532_방학 숙제 파이썬 (if-else vs ceil함수)  (0) 2021.09.22

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

+ Recent posts

티스토리툴바