악곱 == 악성곱슬

책 92p ~ 102p 의 예제

큰 수의 법칙

---

내가 푼 소스코드는 다음과 같다.

import sys

# M <= 10000 일 경우 가능한 풀이 Greedy
N, M, K = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))
li.sort(reverse=True)
answer = 0
while M > 0:
    for j in range(K):
        answer += li[0]  # 가장 큰 수
        M -= 1
    answer += li[1]      # 두 번째로 큰 수
    M -= 1
print(answer)

위 코드는 정렬과 그리디를 통하여 반복문으로 구현한 방법

아래 코드는 동일한 개념이지만 수학적 개념으로 구현한 방법

# M 이 100억 이상 커진다면? 시간초과판정 때문에 Greedy 불가능
# 수학적으로 접근해야함
N, M, K = map(int, sys.stdin.readline().split())
li = list(map(int, sys.stdin.readline().split()))
li.sort(reverse=True)
q = M // (K+1)         # 전체 수열이 반복되는 횟수
r = M % (K+1)          # 나머지 가장 큰 수만 더해지는 횟수
answer = q * (li[0] * K + li[1]) + r * (li[0])
print(answer)

숫자 카드 게임

---

순회하며 가장 가장 작은 값들중 큰 값만 기억하며 넘어가면 되기 때문에 그리디의 정당성을 만족한다고 생각한다.

처음 생각해낸 코드

import sys

N, M = map(int, sys.stdin.readline().split())
li = list()
answer = 0
for i in range(N):
    li.append(list(map(int, sys.stdin.readline().split())))

for i in range(N):
    tmp = min(li[i])
    answer = max(answer, tmp)
print(answer)

위에서 굳이 2차원 배열을 다 받지않고 구현할 수 있을 것 같아서 수정한 코드

import sys

N, M = map(int, sys.stdin.readline().split())
answer = 0
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    row_min = min(row)
    answer = max(answer, row_min)
print(answer)

더욱 줄이는 것은 가독성에 좋지 않을 것으로 판단하여 마무리

min대신 직접 for문을 구현하여 해결 가능

1이 될 때까지

---

해당 문제는 배수가 될 때까지 1을 빼고, 배수가 되면 K로 나누어주면 최적의 해가 보장된다.

K의 배수나 약수로 나누는 옵션을 추가하는 경우에도 그리디가 성립된다.

만약 옵션이 2로 나누기, 3으로 나누기 등과 같이 서로 배수가 아닌 수가 있다면 이는 그리디의 정당성이 성립하지 않고 동적 프로그래밍 방법으로 풀어야 한다.

import sys

N, K = map(int, sys.stdin.readline().split())
count = 0
while N != 1:
    if N % K == 0:
        N = N // K
    else:
        N -= 1
    count += 1
print(count)

이 문제의 경우에도 N의 범위에 따라 풀이가 달라진다.

N의 범위가 크다면 반복문으로 -1씩 빼주는 풀이는 시간초과에 직면한다.

따라서 K의 배수가 한번에 되도록 연산식을 수정해서 반복문의 반복 횟수를 줄인다.

N, K = map(int, sys.stdin.readline().split())
count = 0
while N >= K:
    if N % K == 0:
        N = N // K
        count += 1
    else:
        tmp = (N // K) * K
        count += (N - tmp)
        N = tmp
count += (N - 1)
print(count)