이코테 그리디 파이썬

큰 수의 법칙 

A. 문제
다양한 수로 이루어진 배열을 M번 더하여 가장 큰 수를 만든다.
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.
서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
N은 배열의 크기, M은 숫자가 더해지는 횟수, K는 연속해서 더할 수 있는 횟수.
a. 예를 들면.
[2, 4, 5, 4, 6] 배열, M = 8, K = 3은 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 이다.[3, 4, 3, 4, 3] 배열, M = 7, K = 2은 4 + 4 + 4 + 4 + 4 + 4 + 4 = 28
b. 입력 조건
첫번째 줄에 N (2 <= N <= 1000), M (1 <= M <= 10000), K (1 <= K <= 10000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분하며 1 이상 10000 이하의 수로 주어진다.입력으로 주어지는 K는 항상 M보다 작거나 같다.
c. 출력 조건
첫번째 줄에 답을 출력한다.

#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]
 
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)

# 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) # 최종 답안 출력

숫자카드게임

가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
숫자 카드는 N * M 형태로 놓여 있다.뽑고자 하는 카드가 포함되어 있는 행을 선택한다그 중 가장 숫자가 낮은 카드를 뽑아야 한다최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 한다.
b. 입력 조건
첫번째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 각각 자연수로 주어진다 (1 <= N, M <= 100)두번째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다.각 숫자는 1 이상 10000 이하의 자연수이다.
c. 출력 조건
첫번째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

 

1이 될 때까지

A. 문제
N이 1이 될 때까지 하나를 반복적으로 선택하여 수행하려 한다. 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
N에서 1을 뺀다.N을 K로 나눈다.
N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하라.
a. 입력 조건
첫번째 줄에 N (2 <= N <= 100000)과 K (2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다.입력으로 주어지는 N은 항상 K보다 크거나 같다.
b. 출력 조건
첫번째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

n, k = map(int, input().split())
result = 0 

while n>= k:
  while n%k != 0:
    n -= 1 
    result += 1
  n // k
  result += 1 
while n > 1:
  n -= 1 
  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)

모험가길드

A. 문제
모험가 N명이 있다.모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했다.모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참가해야 여행을 떠날 수 있도록 규정했다.
최대 몇 개의 모험가 그룹을 만들 수 있는가?
몇 명의 모험가는 마을에남아있어도 되기 때문에 모든 모험가를 특정한 그룹에 넣을 필요는 없다
a. 예를 들면.
N = 5 모험가의 공포도 = 2 3 1 2 2
그룹 1에 공포도가 1, 2, 3인 모험가.그룹 2에 공포도가 2, 2인 모험가.총 2개의 그룹을 만들 수 있다.
b. 입력 조건
모험가의 수 N1 <= N <= 100,000각 모험가의 공포도N 이하의 자연수, 각 자연수는 공백으로 구분
c. 출력 조건
여행을 떠날 수 있는 그룹 수의 최댓값

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수

for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
    count += 1 # 현재 그룹에 해당 모험가를 포함시키기
    if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1 # 총 그룹의 수 증가시키기
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화

print(result) # 총 그룹의 수 출력

 

곱하기 혹은 더하기 

A. 문제
각 자리가 숫자(0-9)로만 이루어진 문자열 S가 주어졌다.왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하라.연산 순서는 'x'를 '+'보다 먼저 계산하는 방식이 아닌, 모든 연산은 왼쪽부터 순서대로 이뤄진다고 가정한다.
a. 예를 들면.
S = 02984 이면만들 수 있는 가장 큰 수는 ((((0 + 2) * 9) * 8) * 4) = 576
b. 입력 조건
첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다1 <= S <= 20만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.
c. 출력 조건
첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else:
        result *= num

print(result)​

 

문자열 뒤집기

1439번: 뒤집기

data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우

# 첫 번째 원소에 대해서 처리
if data[0] == '1':
    count0 += 1
else:
    count1 += 1

# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
    if data[i] != data[i + 1]:
        # 다음 수에서 1로 바뀌는 경우
        if data[i + 1] == '1':
            count0 += 1
        # 다음 수에서 0으로 바뀌는 경우
        else:
            count1 += 1

print(min(count0, count1))

 

볼링공 고르기 

A. 문제
A, B 두 사람이 볼링을 치고 있다.두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.볼링공의 무게는 1~M까지의 자연수 형태로 존재한다.
a. 예를 들면.
N = 5, M = 3이며 무게가 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1, 2, 3, 4, 5번으로 부여된다. 이때 두 사람이 고를 수 있는 볼링공의 조합을 구하면, 아래와 같다.
(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)
두 사람이 공을 고를 수 있는 경우의 수는 8가지이다.
b. 입력 조건
첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다1 <= N <= 1,0001 <= M <= 10둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.1 <= K <= M
c. 출력 조건
첫번째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력하라.

n, m = map(int, input().split())
data = list(map(int, input().split()))

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱해주기

print(result)

 

만들 수 없는 금액 

A. 문제
편의점 주인인 동빈이는 N개의 동전을 가지고 있다.N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하라.
a. 예를 들면.
N = 5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정하자. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.
N = 3이고 각 동전이 각각 3원, 5원, 7원이면, 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.
b. 입력 조건
첫째 줄에는 동전의 개수를 나타내는 양의 정수 N1 <= N <= 1,000둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수, 자연수는 공백으로 구분각 화폐 단위는 1,000,000 이하의 자연수
c. 출력 조건
첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력.

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

# 만들 수 없는 금액 출력
print(target)

 

무지의 먹방 라이브 

프로그래머스

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]