이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.
문제 내용
- 문제에서 정의한 큰 수의 법칙운 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
- 이때 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해서 더해질 수 없음
- 그리고 서로 다른 인덱스에 해당하는 수가 같은 경우에는 서로 다른 것으로 간주
- 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 큰 수의 법칙에 따른 결과 출력
입력 조건
- 첫째 줄에 N, M, K의 자연수가 주어지며 각 자연수는 공백으로 구분
- 둘째 줄에 N개의 자연수가 주어지며 각 자연수는 공백으로 구분
- 입력으로 주어지는 K는 항상 M보다 작거나 같음
출력 조건
- 큰 수의 법칙에 따라 더해진 답을 첫째 줄에 출력
입력 예시
5 8 3
2 4 5 4 6출력 예시
46문제 해설
- 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됨
- 연속으로 더할 수 있는 횟수는 최대 K번이므로 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복
소스 코드
# 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): # 가장 큰 수를 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)로 나누어떨어지지 않는 경우도 고려해야 하는데 그럴 때는 M을 (K + 1)로 나눈 나머지만큼 가장 큰 수가 추가로 더해져야 함
- 즉 가장 큰 수가 더해지는 횟수는
int(M / (K + 1)) * K + M % (K + 1) - 위 식으로 가장 큰 수가 더해지는 횟수를 구한 다음, 이를 이용해 두 번째로 큰 수가 더해지는 횟수까지 구할 수 있음
소스 코드
# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))
data.sort() # 입력받은 수 정렬
first = data[-1] # 가장 큰 수
second = data[-2] # 두 번째로 큰 수
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)
result = 0
result += count * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기
print(result) # 최종 답안 출력나의 풀이
- 배열에서 가장 큰 수를 찾기 위해
max()함수를 사용 - 두 번재로 큰 수를 찾기 위해서는 배열에서 가장 큰 수를
remove()함수로 제거 후 다시max()함수를 사용 - M번 반복하여 더하면서 큰 수가 한 번에 최대 K번까지만 더해지도록 가장 큰 수가 몇 번 더해졌는지 셈
소스 코드
import sys
# n: 배열의 크기, m: 더하는 횟수, k: 특정 인덱스의 수를 연속해서 더할 수 있는 횟수
n, m, k = map(int, sys.stdin.readline().rstrip().split())
array = list(map(int, sys.stdin.readline().rstrip().split()))
first = max(array) # 가장 큰 수
array.remove(first)
second = max(array) # 두 번째로 큰 수
result = 0
count = 0 # 가장 큰 수를 더한 횟수
for _ in range(m):
if count < k:
result += first
count += 1
else:
result += second
count = 0
print(result)다른 풀이
- 특정한 수열이 반복된다는 점에 착안하여 M을 (K + 1)로 나눈 몫에 해당 수열을 곱함
- 그리고 M이 (K + 1)로 나누어 떨어지지 않는 경우를 고려하여 나머지에 가장 큰 수를 곱한 값도 결과에 더함
소스 코드
import sys
# n: 배열의 크기, m: 더하는 횟수, k: 특정 인덱스의 수를 연속해서 더할 수 있는 횟수
n, m, k = map(int, sys.stdin.readline().rstrip().split())
array = list(map(int, sys.stdin.readline().rstrip().split()))
first = max(array) # 가장 큰 수
array.remove(first)
second = max(array) # 두 번째로 큰 수
sequence = first * k + second # 반복되는 수열
result = 0
result += sequence * (m // (k + 1))
result += first * (m % (k + 1))
print(result) # 최종 답안 출력
전부인 것처럼, 전부가 아닌 것처럼