[Python] 큰 수의 법칙 ( 2019 국가 교육기관 코딩 테스트)

문제

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

예를 들어 순서대로 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+4+4 인 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보다 작거나 같다.

 

출력 조건

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

 

입력 예시

5 8 3

2 4 5 4 6

출력 예시

46

 

문제 이해

- n,m,k가 들어오는데, n개의 수를 m 번해서 가장 큰 수를 만들어야함.

- 이때, 한 인덱스의 수가 연속으로 k번을 초과해서 쓰이면 안됨.

 

문제 풀이

- 두 가지의 풀이 방법이 있다.

 

첫번째 풀이

- 가장 큰 수 one과 그 다음 큰 수 two를 할당한다. 이를 위해 배열을 오름차순으로 미리 정렬해야함.

- 한 번 더할때마다 횟수 체크 해야한다.

0) 입력  과정 / 변수 : summ = 누적 수, count = 횟수 , one = 가장 큰 수, two = 그 다음 큰 수

1) 가장 큰 수를 one에 저장, 그 다음 큰 수를 two에 저장(정렬을 해서 가장 뒤에거를 one, 그 다음걸 two)

 

2) while문을 통해서 반복을 한다.

2-2 for.. k만큼 반복. one을 summ에 누적한다. 이때, 더할때마다 count도 1 씩 누적한다.

2-3) for 반복 안에서 만약 count가 m이랑 같아지면 종료한다.

 

3) for 반복문 후 summ에 two를 더하고, count에 1을 더한다.

3-1) 만약 count가 m과 같으면 종료.

 

4) 출력

 

n,m,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
one = data[n-1]
two = data[n-2]

summ = 0
count = 0

while True:
    for i in range(k):
        summ += one
        count += 1
        if count == m:
            break
    summ += two
    count += 1
    if count == m:
        break
print(summ)

 

 

두 번째 풀이

- k+1개로 m을 나누는 아이디어

- k+1은 가장 큰 수를 k번 더하고, 그 다음 수를 한번 더한 것 -> 미리 계산해놔야 한다.

- (k+1)로 m을 나눈 몫만큼 총 수를 더하면 되고, 나머지만큼 가장 큰 수를 더해주면 된다.

 

0)입력 / 변수 : total =  k+1한 값, count = total을 더할 횟수, remain = one을 추가로 더해줄 횟수

 

1) 가장 큰 수를 one에 저장, 그 다음 큰 수를 two에 저장(정렬을 해서 가장 뒤에거를 one, 그 다음걸 two)

 

2) k+1한 값과 이 값을 더할 횟수를 미리 구한다.

 

3) 나머지는 곧 one을 추가로 더해야하는 횟수이므로 체크

 

4) k+1한 값을 횟수만큼 더하고 나머지만큼 가장 큰 수를 더해준다.

 

5) 출력

 

n,m,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
one = data[n-1]
two = data[n-2]

total = one*k + two #k+1한 값
count = m // (k+1) #total을 더할 횟수
remain = m % (k+1) #one을 추가로 더해줄 횟수

result = total* count + remain
print(result)