1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# '-'를 기준으로 나눠서 입력 받는다.
equation = input().split('-')
minList = []
print(equation)
# '-'로 나뉜 각 index들의 합을 구해서 리스트로 만든다.
for i in equation:
    # '+'이면 합을 구하면 되므로, 숫자만 있는 리스트로 바꾼 후, sum을 구한다.
    beforeSum = list(map(int, i.split('+')))
    print(beforeSum)
    minList.append(sum(beforeSum))
    # print(beforeSum, minList)
print(minList)
res = minList[0]
for i in minList[1:]:
    res = res - i
print(res)
 
 cs

 

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

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

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

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

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

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

1
2
3
4
5
6
7
8
n = 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

 

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

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

[백준] 6768_Don’t pass me the ball! 파이썬 (combination함수)  (0) 2021.10.09
[백준] 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
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

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

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

[백준] 6768_Don’t pass me the ball! 파이썬 (combination함수)  (0) 2021.10.09
[백준] 11399_ATM 파이썬 (그리디 알고리즘 / 정렬)  (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

 

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

특히 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

 

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

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

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

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

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

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
L = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
k = math.ceil(A / C)
m = 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

 

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

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

[백준] 7568_덩치 파이썬  (0) 2021.09.27
[백준] 2798_블랙잭 파이썬 (combination함수 vs 3중for문)  (0) 2021.09.26
[백준] 2953_나는 요리사다.  (0) 2021.09.21
[백준] 2292_벌집 파이썬  (0) 2021.09.19
[백준] 11650_좌표 정렬하기 파이썬 (lambda 활용)  (0) 2021.09.19

파이썬의 경우, 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

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

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

[백준] 2798_블랙잭 파이썬 (combination함수 vs 3중for문)  (0) 2021.09.26
[백준] 5532_방학 숙제 파이썬 (if-else vs ceil함수)  (0) 2021.09.22
[백준] 2292_벌집 파이썬  (0) 2021.09.19
[백준] 11650_좌표 정렬하기 파이썬 (lambda 활용)  (0) 2021.09.19
[백준] 1672_DNA 해독 파이썬  (0) 2021.09.18

벌집의 숫자가 어떻게 늘어났을 경우, 경로가 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())
i = 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

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

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

[백준] 5532_방학 숙제 파이썬 (if-else vs ceil함수)  (0) 2021.09.22
[백준] 2953_나는 요리사다.  (0) 2021.09.21
[백준] 11650_좌표 정렬하기 파이썬 (lambda 활용)  (0) 2021.09.19
[백준] 1672_DNA 해독 파이썬  (0) 2021.09.18
[백준] 1225_이상한 곱셈 파이썬 (시간초과 문제 해결하기)  (0) 2021.09.18

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

 

처음에는 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

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

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

[백준] 2953_나는 요리사다.  (0) 2021.09.21
[백준] 2292_벌집 파이썬  (0) 2021.09.19
[백준] 1672_DNA 해독 파이썬  (0) 2021.09.18
[백준] 1225_이상한 곱셈 파이썬 (시간초과 문제 해결하기)  (0) 2021.09.18
[백준] 2566_최댓값 파이썬  (0) 2021.09.16

+ Recent posts

티스토리툴바