이것이 코딩 테스트다 그리디에 나오는 예제를 제 방식대로 수정하여 풀었습니다.
큰 수의 법칙
배열의 크기 n, 숫자를 더할 횟수 m, 연속해서 같은 숫자를 사용할 수 있는 횟수 제한 k
숫자 배열을 입력 받아서 만들 수 있는 가장 큰 수 출력
=> 가장 큰 수를 제한까지 더하고 두 번째 큰 수를 한 번 더하고 다시 가장 큰 수를 더하는 방식으로 반복
|
1
2
3
4
5
6
7
8
9
10
11
12
|
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
total = 0
data.sort()
count = m // (k + 1)
total += (m -count) * data[-1]
total += count * data[-2]
print(total)
|
cs |
책에서는 가장 큰 수가 나오는 횟수를 (int(m / (k + 1) * k ) + (m % k) 로 구해서 곱해줬는데
가장 큰 수가 나오는 횟수를 구하지 않고, 두 번째 큰 수가 나오는 수를 구해서 계산해주는 편이 더 깔끔한 것 같다.
그리고 / 대신 // 을 사용해서 int() 로 감싸주는 부분을 생략했다.
1이 될 때 까지
n 이 1이 될 때까지 k로 나누거나, 일을 빼는 연산을 할 수 있다.
최소한의 연산으로 n이 1이 되려면 몇 번 연산해야 하는지 출력하라.
=> k가 1이면 빼기와 같고 1보다 크면 연산 횟수가 훨씬 줄어든다.
따라서 나눗셈 연산을 최대한 많이 하면 최소한의 연산 횟수가 된다.
n을 k로 나눈 나머지 많큼 횟수에 더해준다. k의 배수가 될 때 까지 -1을 해주는 것과 동일
n이 k 보다 크거나 같일 때만 1을 더해주는 이유는 n이 k 보다 작으면 나눗셈 연산을 할 수 없기 때문이다.
|
1
2
3
4
5
6
7
8
9 10 11 12 |
n , k = map(int, input().split())
cnt = 0
while n > 1:
cnt += (n % k)
if n >= k : cnt += 1 n = n // k
print(cnt)
|
cs |
'IT > Python' 카테고리의 다른 글
| [codility] Greedy TieRopes (0) | 2023.03.29 |
|---|---|
| [codility] Greedy MaxNonoverlappingSegments (0) | 2023.03.29 |
| 두 수의 합 (이중 for문 / 투 포인터 / Hash) (0) | 2023.03.15 |
| [프로그래머스] 파일명 정렬 (안정 정렬이란?) (0) | 2022.08.09 |
| 파이썬 리스트 선언시 주의 (0) | 2021.07.02 |