1 분 소요

큰 수의 법칙

문제

큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙이다. 단 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

입력조건

  • 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

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

출력조건

  • 첫째 줄에 큰 수 의 법칙에 따라 더해진 답을 출력한다.

입력예시

5 8 3
2 4 5 4 6

출력예시

46

나의 코드

첫 번째 시도.

N,M,K=map(int,input().split())

num=list(map(int,input().split()))
num=sorted(num)

print((M//K)*(K*num[-1])+(M%K)*(num[-2]))

🌝 Thinking

반례가 존재함(앞에서 부터 큰 수를 꽉꽉채워가면서 나오는 나머지임으로 정확하지가 않음.)

떠올렸던 원리를 그대로 따라가서 구현했어야했음. 그래서 그리디?

두 번째 시도

N,M,K=map(int,input().split())

num=list(map(int,input().split()))
num=sorted(num)

first = num[N-1]
second = num[N-2]

sum=0

while True:
    for i in range(K):
        sum+=first
        M-=1
    sum+=second
    M-=1
    if M==0:
        break

print(sum)

🌝 Thinking

정답임을 확신하고 답안 알고리즘과 대조를함. 두번 째 시도 또한 문제가 있었음.

M==0이면 루프를 빠져나오는 조건을 맨 마지막 한번 만 주었기에 M=1일때 오답이 나옴.

답안 예시1

N,M,K=map(int,input().split())

num=list(map(int,input().split()))
num=sorted(num)

first = num[N-1]
second = num[N-2]

sum=0

while True:
    for i in range(K):
        if M==0:
            break
        sum+=first
        M-=1

    if M==0:
        break
    sum+=second
    M-=1

print(sum)

아까웠군,,,

답안예시2

시간을 단축 시키는 좋은 알고리즘.

N,M,K = map(int,input().split())
data=list(map(int,input().split()))

data.sort()
first = data[N-1]
second = data[N-2]

count = (M//(K+1))*K
count+= M%(K+1)

result = 0 
result += count * first
result += (M-count)*second

print(result)

💡 깨달은 점.

  1. 루프를 빠져나올때 항상 꼼꼼히 생각하는 연습을 해야겠다.

  2. 연산횟수가 1억이 넘어간다면 …? 내가 떠 올렸던 첫번째 발상을 조금더 꼼꼼이 다듬었다면 충분히 좋은 알고리즘을 만들 수 있었다. 엄밀하게 코드를 짜는 연습을 더 해야겠다.

출처

이것이 코딩 테스트다 - 나동빈 저

댓글남기기

참고