Iridescent Seraphim

Where Code Meets Life

recent posts

about

#2 큰 수의 법칙: 그리디 알고리즘으로 문제 해결

문제: 큰 수의 법칙은 주어진 배열에서 특정 수를 M번 더하여 가장 큰 수를 만드는 법칙으로, 각 인덱스의 수는 K번까지만 연속해서 더할 수 있다. 예를 들어 배열이 2, 4, 5, 4, 6일 때 M이 8, K가 3일 경우 결과는 46이며, 배열이 3, 4, 3, 4, 3일 때 M이 7, K가 2일 경우 결과는 28이 된다. 배열의 크기 N, 숫자가 더해지는 횟수 M, K를 입력받아 큰 수의 법칙에 따른 결과를 출력하라.

입력 조건:
– 첫째 줄에 N(2 ≦ N ≦ 1,000), M(1 ≦ M ≦ 10,000), K(1 ≦ K ≦ 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
– 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다.
– 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건:
– 첫째 줄에 상단의 큰 수의 법칙에 따라 더해진 답을 출력한다.
# 큰 수의 법칙을 구현한 Python 코드 1번 문제 풀이
# 입력 받기
N, M, K = map(int, input().split())
numbers = list(map(int, input().split()))
# 가장 큰 수와 두 번째 큰 수를 찾기
numbers.sort()
first = numbers[-1]  # 가장 큰 수
second = numbers[-2]  # 두 번째 큰 수
# 큰 수의 법칙을 이용하여 계산
# 첫 번째 수가 더해지는 횟수
count_first = (M // (K + 1)) * K + (M % (K + 1))
# 총 합 계산
result = count_first * first + (M - count_first) * second
# 결과 출력
print(result)
# 2번 문제풀이
# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
numbers = list(map(int, input().split()))
numbers.sort() # 입력받은 수들 정렬하기
first = numbers[n - 1] # 가장 큰 수
second = numbers[n - 2] # 두 번째로 큰 수
result = 0
while True:
  for i in range(k): # 가장 큰 수를 K번 더하기
    if m == 0: # m이 0이라면 반복문 탈출
      break
    result += first
    m -= 1 # 더할 때마다 1씩 빼기
  if m == 0: # m이 0이라면 반복문 탈출
    break
  result += second # 두 번째로 큰 수를 한 번 더하기
  m -= 1 # 더할 때마다 1씩 빼기
print(result) # 최종 답안 출력


∴ 이를 이용한 문제 답안은 아래와 같다.이 문제를 해결하기 위해서는 반복되는 수열을 이해해야 하며, 가장 큰 수와 두 번째로 큰 수의 합이 일정하게 반복되는 성질이 있다. 반복되는 수열의 길이는 K+1이고 M을 (K+1)로 나눈 몫이 반복 횟수가 되며, 여기에 K를 곱하면 가장 큰 수의 등장 횟수가 된다. M이 (K+1)로 나누어 떨어지지 않을 때는 나머지만큼 가장 큰 수가 더해져야 하며, 이를 고려한 횟수는

int(M / (K + 1)) * K + M % (K + 1)

로 계산된다. 이를 이용한 답안은 아래와 같다.

# 3번 문제풀이
# N, M, K를 공백으로 구분하여 입력 받기
n, m , k = map(int, input().split())
#N개의 수를 공백으로 구분하여 입력받기
numbers = list(map(int, input().split()))
numbers.sort() # 입력받은 수 정렬
first = numbers[n - 1] # 가장 큰 수
second = numbers[n - 2] # 두 번째로 큰 수
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)
result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기
print(result) # 최종 답안 출력

Posted in

Leave a comment