이것이 취업을 위한 코딩 테스트다 CHAPTER 3 그리디

현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

문제 2. 큰 수의 법칙

'''

    Chapter 3. 그리디 : 큰 수의 법칙

    접근법 1

        (가장 큰 수를 K번 더하고 두번째 큰 수 1번 더하기)를 for문을 이용하여 반복하기

       

    접근법 2

        (가장 큰 수를 K번 더하고 두번째 큰 수 1번 더하기)를 반복 -> 반복 주기 (K+1)

        가장 큰수를 더할 횟수 구하기 == (M-cnt)

           

        두번째 큰 수 더할 횟수 == cnt

            1사이클에 1번

            cnt = M//(K+1)

'''

import sys
input = sys.stdin.readline

# 배열의 크기, 숫자가 더해지는 횟수, 반복 가능 수
N,M,K = map(int,input().split())

# 배열
arr = list(map(int,input().split()))
arr.sort(reverse=True)

# 정답
answer = 0

# 특정 인덱스 연속 횟수
k = 0
for i in range(M):
    k += 1
    # K번 같은 수를 더했는가?
    if k == K:
        # 2번째 큰 수 더하기 + k 초기화
        answer += arr[1]
        k = 0
    # 아니라면
    else:
        # 가장 큰 수 더하기
        answer += arr[0]

print(answer)


##############################################
# 배열의 크기, 숫자가 더해지는 횟수, 반복 가능 수
N,M,K = map(int,input().split())

# 배열
arr = list(map(int,input().split()))
arr.sort(reverse=True)

# 가장 큰 수
f = arr[0]
# 두번째로 큰 수
s = arr[1]

# 두번째로 큰 수 더한 횟수
cnt = M//(K+1)
answer = f*(M-cnt) + s*cnt
print(answer)

 

---

문제 3. 숫자 카드 게임

'''

    Chapter 3. 그리디 : 숫자 카드 게임

    접근법 1

        각 행의 가장 작은 수 중 가장 큰 수!

        각 행의 가장 작은 수를 r_min(list)에 저장 -> r_min 중 가장 큰 수 출력

'''

import sys
input = sys.stdin.readline

# 행, 열
N,M = map(int,input().split())

# 각 행에서 가장 작은 수
r_min = []

for i in range(N):
    # i번째 행
    r = list(map(int,input().split()))
    # i번째 행에서 가장 작은 수
    r_min.append(min(r))

# 각 행에서 가장 작은 수 중 가장 큰 수
print(max(r_min))

 

---

문제 4. 1이 될 때까지

'''

    Chapter 3. 그리디 : 1이 될 때까지

    접근법 1

        N이 1이 될 때까지 반복 -> 횟수를 정할 수 없으므로 while문

        K로 나누어 떨어지면 K로 나누고 아니면 1빼기

'''

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
cnt = 0
while N != 1:
    cnt += 1
    # N이 K로 나누어떨어지면 나누기
    if N%K == 0:
        N /= K
    # 아니면 1을 뺀다
    else:
        N -= 1

print(cnt)