그리디 : 큰 수의 법칙 [ 이것이 코딩테스트다 ] [ Python ]

문제

 

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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 = map(int, input().split())
print(n, m, k)
# k 는 한 숫자가 더해질수 있는 횟수, m 은 연산 횟수, n 은 배열의 크기
data = list(map(int, input().split()))
print(data)

result = 0
# 결과를 저장

data.sort()
# 입력한 데이터 정렬

big = data[len(data) - 1]
# 가장 큰 값
littleBig = data[len(data) - 2]
# 두 번째로 큰 값
print(big)
print(littleBig)

end_loop = 0
# 루프를 끝내기 위한 변수 end_loop
while end_loop != 1:
    # end_loop 가 1이 되면 종료된다.
    for i in range(k):
        # 한 숫자가 더해질수 있는 횟수인 k 변수 만큼 for 루프가 반복된다
        if m <= 0:
            # 연산횟수인 m 이 0 과 같아지거나 적어지면 종료된다.
            end_loop = 1
            break
        # 가장 큰값인 big 변수를 result 에 더해준다.
        result += big
        print("result1:",result)
        # 연산횟수인 m 변수를 1 빼준다.
        m -= 1
        print("m:",m)
    
    if m <= 0:
        end_loop = 1
        break
    # 두번째로 큰값인 littleBig 변수를 result 에 더해준다.
    result += littleBig
    print("result2:",result)
    # 연산횟수인 m 변수를 1 빼준다.
    m -= 1
    print("m2:",m)

print(result)

 

저자 코드

# 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] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)

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

print(result) # 최종 답안 출력

---

회고

확실히 파이썬에 대한 이해가 부족하다는 것을 느낀 문제이다. 그래서 지저분한 상태인 나의 코드를 그대로 업로드 하였다.

end_loop 변수를 이용해서 while 루프를 빠져나가게 만들고 싶었다. 왜 break 를 안쓰고 그렇게 했냐고 한다면.. 

실수로 일어날 수 있는 "while true 상태의 무한루프를 최대한 방지하고 통제하고 싶어서" 가 이유일 것 같다.

하지만 이 end_loop 를 사용하는 방법은 내가 원하지 않는 결과를 나오게 했다. 결과적으로 루프를 빠져나오지 못했다.

결국 break 를 사용하니 뜻대로 작동했다.

왜 생각대로 동작을 안했는지 파이썬에대한 공부가 필요하다.

 

마지막으로 문제를 직면하게되어서 다행이다.