[알고리즘] 그리디알고리즘_큰 수의 법칙(파이썬 나눗셈의 몫 구하는 법, 파이썬 공백 구분하여 입력받는 법)

 

[큰수의 법칙 문제 설명]

-난이도 : ★☆☆

-풀이시간 : 30분

-시간 제한 : 1초

-메모리 제한 128MB

-기출 : 2019 국가 교육기관 코딩 테스트

-출처 : 이것이 코딩 테스트다 with 파이썬문제 p.92

 

-문제 :

요약동빈이의 큰수의 법칙은 배열이 있을 때 주어진 수들을 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으로 이루어진 배열이 있을 땐 4+4+4+4+4+4+4+4 가 된다. 

배열의 크기 n, 숫자가 더해지는 횟수 m, 연속가능한 수 k가 주어질 때 큰 수를 구하시오

-입력예시 5 8 3 2 4 5 4 6

-출력예시 46

 

 

[큰수의 법칙 답안1]

# n, m, k를 공백으로 구분하여 입력받기
# n은 배열의 크기, m은 숫자가 더해지는 횟수
# 특정한 인덱스에 해당하는 수가 연속해서 k번을 초과할 수 없음(k번까지만 더해질 수 있음)
n, m, k = map(int, input().split())

# n개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))  # 공백으로 구분하여 입력 받고 list에 담기

data.sort()  # 오름차순으로 정렬하기(대입 필요 x)
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)  # 최종 답안 출력

 

[큰 수의 법칙 답안2]

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

#n개의 수를 공백으로 구분하여 입력받기 (위의 코드를 list로 감싸주면 된다.)
data = list(map(int, input().split()))

#오름차순으로 정렬해주기
data.sort()
first = data[n-1] #가장 큰 수
second = data[n-2] #두번째로 큰 수

#가장 큰 수가 더해지는 횟수 계산 : 반복 수열*k + m이 k+1로 나누어떨어지지 않는 경우
count = int(m/(k+1))*k + m%(k+1)

#계산하기
result = 0
result += first*count   #가장 큰 수 더하기
result += second*(m-count) #두 번째로 큰 수 더하기

#결과 출력
print(result)

 

[답안2 해설]

 

[파이썬 상식]

 

>> 파이썬 나눈셈 몫 구하는 법

 

1. 파이썬에는 //연산자를 이용하거나

ex) 5//3 = 1

 

2. int(a/b)를 이용한다.

ex) int(5//3)

 

>> 파이썬 공백 구분하여 입력 받기

 

1.여러개의 수를 공백 구분하여 변수에 입력받기

ex) n,m,k = map(int, input().split())

 

2.여러개의 수를 공백 구분하여 입력받아 list로 변환하기

ex) data = list( map(int, input().split()) )