Greedy(탐욕법) - 현재상황에서 지금 당장 좋은 것만 고르는 방법!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
# 거스름돈
# 파이썬
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
|
cs |
|
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
|
큰수의 법칙
n,m,k = map(int, input().split())
data = list(map(int,input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
result = 0
while True:
for i in range(k):
if(m==0):
break
result += first
m -=1
if(m==0):
break
result += second
m -=1
print(result)
|
cs |
위의 코드에서 반복되는 규칙을 파악한 후 다시 짠 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# N,M,K를 공백으로 구분하여 입력받기
n,m,k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int,input().split()))
data.sort() # 입력받은 수 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두번째로 큰 수
# 가장 큰 수가 더해지는 횟수 계산
count = int(m/(k+1))*k
count += m%(k+1)
result = 0
result += count*first # 가장 큰수 더하기
result += (m-count) * second # 두 번째로 큰 수 더하기
print(result) # 최종 답안
|
cs |
숫자 카드 게임 p96
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
n,m = map(int,input().split())
result = 0
# min()
for i in range(n):
data = list(map(int,input().split()))
# 현재 줄에서 '가장 적은 수 ' 찾기
min_value = min(data)
# '가장 적은 수' 들 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result)
# 또는 이중 for문
for i in range(n):
data = list(map(int,input().split()))
# 현재 줄에서 '가장 적은 수 ' 찾기
min_value = 10001 for i in data:
min_value = min(min_value,a)
result = max(min_value,result)
print(result)
|
cs |
|
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
|
# 1이 될 때까지
n,k = map(int,input().split())
result =0
while n>=k:
while n%k !=0:
n-=1
result+=1
n //=k
result +=1
print(result)
# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)
|
cs |
'알고리즘 문제 > 자료구조&알고리즘' 카테고리의 다른 글
| 정렬 예제 (0) | 2020.10.22 |
|---|---|
| 정렬 (0) | 2020.10.21 |
| DFS/BFS 예제 (0) | 2020.10.21 |
| DFS(Depth First Search)/BFC(Breadth First Search) (0) | 2020.10.21 |
| 구현 (0) | 2020.10.19 |