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

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


등급이 실버III 이라고 되어있긴 하지만, 의외로 간단하게 해결이 가능하다.

다만, 그리디 알고리즘인만큼, 숫자들에 대한 규칙을 잘 찾아내는 것이 좋다고 생각된다.

1
2
3
4
5
6
7
8
= int(input())
line = list(map(int, input().split()))
line.sort() # 가장 큰 수를 가장 마지막으로 보내버리자
total = 0
for i in range(n):
    for j in range(i+1):
        total += line[j]
print(total)
cs

가장 큰 숫자를 가장 뒤로 옮기면서, 정렬시켜서 다음과 같이 덧셈을 처리하는 과정을 찾을 수 있다.

1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 3 = 9
1 + 2 + 3 + 3 + 4 = 13
==> 1 + 3 +  6 + 9 + 13 = 32

이를 코드로만 옮겨서 만들면 끝!

 

 

 

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

 

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

 


일단 코드는 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
cityNum = int(input())
roads = list(map(int, input().split()))
price = list(map(int, input().split()))
 
minPrice = price[0]  # 주유소 리터당 가격이 가장 작은 것
res = 0
# 마지막 도시(=도착지)의 L는 따질 필요가 없다.(=n-1 도시의 수 만큼 반복)
for i in range(cityNum-1):
    if minPrice <= price[i]:
        res = res + (minPrice * roads[i])
    elif minPrice > price[i]:
        minPrice = price[i]
        res = res + (minPrice * roads[i])
print(res)
cs

 

전략 설명
[예시 그림]
   3      2      1
A ---> B ---> C ---> D
5L     2L     3L     1L

1. 첫 번째 도시에서는 무조건 다음 도시까지의 거리만큼을 주유해야 한다.
따라서, 가장 작은 주유소 리터당 가격(=minPrice)를 첫 번째 도시에서 가지게 된다.
[예시] A도시에서 주유를 하면 무조건 5L 를 3만큼 가야 한다.
따라서, minPrice = 5로 시작해서, res=5L*3이 된다.

2. 다음 도시부터는 도시에서 가지는 리터당 주유소 가격이 가장 작은 값으로 계속 그다음 도시까지의 거리만큼 넣으면 된다.
[예시] B도시에서 주유를 하면 이전도시(A도시)보다 주유소 리터당 가격이 작으므로 (5L > 2L), minPrice = 2L로 바뀌고,
다음 도시(C도시)까지의 거리만큼 이동해서 res = res + (2L * 2) 가 된다.

3. 마지막 도시에 도착할 때까지 2번(minPrice와 res 업데이트) 반복
[예시] C도시에서 B도시의 리터당 주유소 가격이 더 크므로 (2L < 3L), 
더 작은 가격을 가졌던 이전 도시(B도시)에서 C에서 D로 가는 거리만큼 더 넣어야 최소비용이 들어감을 알 수 있다.
따라서, res = res + (2L * 1)이 된다.

최종 값은 (5L*3) + (2L * 2) + (2L * 1) 가 된다.



반성
전략 자체에 대해서 떠오르는데 어려웠다...

 

 

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

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

 


너무 복잡하게 생각하지 않으면 간단하게 해결할 수 있는 구현(브루트포스) 문제이다.

특히 for문을 잘 이용해서 처리하면 되므로, for문을 통해서 잘 해결할 수 있는 전략을 세우는 것이 중요하다.

코드는 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
num = int(input())
people = []
 
for i in range(num):
    people.append(list(map(int, input().split())))
 
rank = []
for i in range(num):
    rankNum = 1
    for j in range(num):
        if (people[i][0< people[j][0]) and (people[i][1< people[j][1]):
            rankNum += 1
    rank.append(rankNum)
 
for i in rank:
    print(i, end = ' ')
cs

 

 

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

 

7568번: 덩치

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩

www.acmicpc.net

 


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(num3))  처럼 조합들을 넣고 싶은 변수 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()))
= 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

 


일단 가장 먼저 성공했던 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
days = int(input())
korean =  int(input())
maths =  int(input())
maxKorean =  int(input())
maxMaths =  int(input())
if korean % maxKorean != 0:
    koreanDays = korean // maxKorean + 1
else:
    koreanDays = korean // maxKorean
if maths % maxMaths != 0:
    mathsDays = maths // maxMaths + 1
else:
    mathsDays = maths // maxMaths
maxDays = max(koreanDays, mathsDays)
print(days - maxDays)
 
cs

if-else문을 통해서 나머지가 있고 없고에 따라서 처리를 한다.


그런데 이 방법보다 훨씬 쉬운 방법은 math 모듈을 import 해서 ceil() 함수를 사용하는 것이다.

다음과 같은 코드를 사용하면 된다.

1
2
3
4
5
6
7
8
9
10
import math
= int(input())
= int(input())
= int(input())
= int(input())
= int(input())
= math.ceil(A / C)
= math.ceil(B / D)
free = max(k, m)
print(L - free)
cs

 

 

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

 

5532번: 방학 숙제

한 줄에 하나씩 총 다섯 줄에 걸쳐 L, A, B, C, D가 주어진다. (2 ≤ L ≤ 40, 1 ≤ A, B ≤ 1000, 1 ≤ C, D ≤ 100) 항상 방학 숙제를 방학 기간내에 다 할 수 있는 경우만 입력으로 주어진다.

www.acmicpc.net

 


파이썬의 경우, list를 활용해서 간단하게 해결할 수 있다.

먼저 예제의 입력을 map을 통해서 contestant변수에 잘 넣어준다.

그다음, 각각의 index에 들어있는 숫자들의 합을 구한다.

마지막으로, 숫자들의 합 중에서 가장 큰 수의 index+1(index는 0부터 시작하기 때문)을 출력하고, 해당 수를 출력해주면 된다.

1
2
3
4
5
6
contestant = []
cont_sum = []
for a in range(5):
    contestant.append(list(map(int, input().split())))
    cont_sum.append(sum(contestant[a]))
print(cont_sum.index(max(cont_sum))+1, max(cont_sum))
cs

 

 

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

 

2953번: 나는 요리사다

"나는 요리사다"는 다섯 참가자들이 서로의 요리 실력을 뽐내는 티비 프로이다. 각 참가자는 자신있는 음식을 하나씩 만들어오고, 서로 다른 사람의 음식을 점수로 평가해준다. 점수는 1점부터 5

www.acmicpc.net


벌집의 숫자가 어떻게 늘어났을 경우, 경로가 1씩 늘어나는지 알기만 하면 간단하다.

1을 기준으로 봤을 때, 각 경로가 1씩 늘어나는 기점(=최댓값)이 1 - 7 - 19 - 37 - 61 --- 로 증가한다.

그리고 이 사이의 숫자는 6 - 12 - 18 --- 6의 배수로 증가한다.

따라서, 다음과 같이 코드를 짜면 간단히 해결된다.

1
2
3
4
5
6
7
8
9
10
11
num = int(input())
= 0
prevNum = 1
while True:
    if num > prevNum + 6 * i:
        prevNum += 6 * i
        i += 1
    else:
        print(1 + i)
        break
 
cs

 

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

 

2292번: 벌집

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌

www.acmicpc.net


전략적으로는 어떻게 해야할지 알았는데, 계속 중복에 대한 숫자에 대해서 처리를 해야해서 오래 고민하고 검색을 해야했던 문제이다.

 

처음에는 dict를 사용해서 넣으려고 했지만, dict는 무조건 중복 key값에 대해서는 update를 해버리기 때문에 사용을 할 수가 없었다.

결국, list를 활용할 수 밖에 없는 상황이다.

 

여기서 key값을 sort(정렬)시키는 방법은 lambda를 활용하는 방법이다.

첫 번째 인자인 x[0]부터 정렬을 한 후, x[1]을 정렬해주는 방법으로 다음과 같은 공식(?)을 활용하면 된다.

array.sort(key=lambda x: (x[0], x[1]))

 

결론적으로는 다음과 같은 코드를 짜면 된다.

1
2
3
4
5
6
7
8
9
10
import sys
num = int(sys.stdin.readline())
arr = []
for _ in range(num):
    arr.append(list(map(int, sys.stdin.readline().split())))
arr.sort(key=lambda x: (x[0], x[1])) #lambda에 대해서 제대로 알고 있자...
# print(arr)
for i in arr:
    print(i[0], i[1])
 
cs

꽤 많이 활용될 수 있는 lambda이기 때문에 제대로 익혀두는 것이 좋겠다!

 

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

 

11650번: 좌표 정렬하기

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

www.acmicpc.net


Pandas나 Numpy를 활용하면 분명 표를 바로 그릴 수 있는 방법이 있겠지만,

이 모듈들은 대부분의 코딩테스트에서는 사용할 수 없으므로 사용하지 않고 구현을 해보기로 했다.

덕분에 내가 아는 방법 내에서는 함수를 사용해서 위의 표를 일일이 경우의 수대로 if문으로 만들어서 리턴시키는 방법뿐이었다.

 

다음의 코드대로 했더니 문제를 맞힐 수 있었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def dnaTable(col, row):
    if col == 'A' and row == 'A':
        return 'A'
    if col == 'A' and row == 'G':
        return 'C'
    if col == 'A' and row == 'C':
        return 'A'
    if col == 'A' and row == 'T':
        return 'G'
 
    if col == 'G' and row == 'A':
        return 'C'
    if col == 'G' and row == 'G':
        return 'G'
    if col == 'G' and row == 'C':
        return 'T'
    if col == 'G' and row == 'T':
        return 'A'
 
    if col == 'C' and row == 'A':
        return 'A'
    if col == 'C' and row == 'G':
        return 'T'
    if col == 'C' and row == 'C':
        return 'C'
    if col == 'C' and row == 'T':
        return 'G'
 
    if col == 'T' and row == 'A':
        return 'G'
    if col == 'T' and row == 'G':
        return 'A'
    if col == 'T' and row == 'C':
        return 'G'
    if col == 'T' and row == 'T':
        return 'T'
 
num = int(input())
dnaCode = list(map(str, input()))
= 0
while(i != num):
    i += 1
    decode = []
    decode.append(dnaTable(dnaCode[num-i], dnaCode[num-i-1]))
    # print(dnaCode)
    if len(dnaCode) != 1#dnaCode가 비어있지 않으면
        dnaCode.pop()
        dnaCode.pop()
        dnaCode.append(decode[0])
    else:
        break
print(dnaCode[0])
 
cs

 

이게 맞나 싶을 정도로 함수 부분의 코드가 길어진 부분에 대해서 끊임없이 의심하면서도 결국 노가다성의 코드를 만들었다.

밑의 코드에서는 while문을 활용해서 decode에 계속 해독된 코드 부분을 집어넣고

dnaCode에서 해독해야 할 부분의 2 문자를 빼서 해독된 부분을 새로 추가시켜주는 방법이다.

이때, dnaCode에 우리가 원하는 최종 문자 1개가 남았을 경우, while문에서 break 하고,

해당 문자를 출력해주기만 하면 된다.

 

사실 언뜻 보기만 해도 꽤나 지저분한 코드라고 스스로도 생각하고 있다.

뭔가 더 깔끔한 방법의 코드가 있다면.. 혹은 조언을 받을 수 있다면, 추후에 다시 이 해당 문제를 수정해볼 생각이다...

 

 

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

 

1672번: DNA 해독

N개의 A, G, C, T로 구성되어 있는 DNA 염기서열이 있다. 그리고 우리는 이 염기서열을 아래의 표를 이용하여 해독을 해야 한다. 해독 방법은 염기 서열에서 제일 끝에 있는 두 개의 염기를 An-1, An이

www.acmicpc.net

+ Recent posts