예제1. 큰 수의 법칙

문제 이해

핵심) 배열의 원소를 N번 더하여 갖아 큰 수 만들기

• 특정 원소는 k번 초과하여 더해질 수 없음
• 서로 다른 인덱스의 수가 같을 때 = 서로 다른 것으로 간주
• k는 M보다 항상 작거나 같다
• 배열의 크기 N, 숫자 더해지는 횟수 M, 제한 K일때 위 법칙에 따라 더해진 값을 출력

해결 아이디어

전형적 그리디.
가장 큰 수를 k번 더하고, 두번째 큰 수를 한번 더한뒤, 또 다시 큰 수를 k번 더하기를 반복. (더하기 횟수는 N번)

내가 짠 코드

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

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

data.sort(reverse=True) # 오름차순 정렬

k_cnt = 0
res = 0

for _ in range (m) : # 총 m번 더하기
  if k_cnt >= k : # k번 초과하여 더했을때
     res += data[1] # 두번째로 큰 수 한번 더해주고
     k_cnt = 0 # k카운트 초기화
     continue
  res += data[0] # 가장 큰 수 더해주고
  k_cnt += 1 # k카운트 재기
print(res)

더 똑똑하게 풀기

M이 100억 이상으로 커지면 시간 초과 판정을 받는다.

# 수학적으로 더 똑똑하게 풀기


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

data.sort()
first = data[n-1]
second = data[n-2]

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

result = 0
result += (cnt) * first
result += (m-cont) * second

print(result)

• 식 유도 과정
  

예제 2 숫자 카드 게임

문제 이해

핵심) 가장 높은 숫자가 쓰인 카드를 뽑되, 룰을 지키며 카드를 뽑아야한다.

• 행을 선택하고 -> 선택한 행 중 가장 낮은 숫자 뽑아야함
• 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야

처음든 생각

각 행의 최솟값이 제일 큰 행을 뽑으면 되지 않나..?
이렇게 간단하다고..?

핵심 개념

처음든 생각에서 한 생각이 맞음.
각 행마다 가장 작은 수를 찾은 뒤 그 수 중에서 가장 큰 수 찾기'

처음 쓴 코드

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

res = 0

for i in range(n) :
  data = list(map(int, input().split()))
  min_res = min(data)
  res = max(res, min_res)

print(res)

댓츠롸잇

예제3 1이 될때까지

문제 이해

N이 1이 될때까지 다음을 반복수행한다.
1) N에서 1 빼기
2) N을 K로 나누기 (단, n이 k로 나누어떨어질때만)

n을 1로 만드는 최소 갯수는?

처음 든 생각

직관적으로는 나누기를 많이 할 수록 쌉이득아닌가?

근데 장담 못하겠는게,혹시 당장 나누기를 많이 하는 것보다, -1을 함으로써 적절한 수로 맞추는게 더 도움 되는 짓 아닐까..?

그래도 대충 합리화하자면,
1) /n을 한번 하는 건 곧, -1을 n번 하는 것과 같다.
2) 적절한 수를 맞추려 -1을 n번 해봤자 어차피 ..어쩌구...

책에서 읽은 개념

k가 2 이상일때, k로 나누는 것이 1을 빼는것보다 "항상" 빠르게 N의 값을 줄일 수 있다.

쩝.. 그렇다네 좀 더 수학적으로 확실히 증명하고싶은디..

처음 쓴 코드

n, k = map(int, input().split())
cnt = 0

while(n != 1) :
  if (n % k == 0) :
    n /= k
    cnt += 1
  else :
    n -= 1
    cnt += 1

print(cnt)

댓츠롸잇~