큰 수의 법칙
•
가장 큰 수와 두번째로 큰 수만 골라내면 되는 문제
•
‘가장 큰 수를 k번 더하고, 두 번째로 큰 수를 한 번 더하는 연산’ 을 길이 M 이 될때까지만 반복
# 큰 수의 법칙
# 주어진 수들을 M번 더해서 가장 큰 수를 만들기
# 단, 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해서 더해질 수는 없다.
# 단, 서로 다른 인덱스에 해당하는 수가 같아도 다른 것으로 간주
# 첫째줄에 N, M, K 가 공백으로 구분되어 입력된다.
# 둘째줄에 N개의 자연수가 주어지고, 공백으로 구분한다.
# K는 항상 M보다 작거나 같다.
# 여기서 주의할 점은 서로 인덱스는 다르지만 같은 숫자일 경우, 두번째로 큰 수도 반복해서 두번 쓸 수 있으니, 경우 수를 나눠야하는거 아닌가 할 수 있지만, 다르지 않다. 결국 한번 더하고 가장 큰 수를 K번 더하는 것과 결과는 같기 때문
n,m,k = map(int, input().split())
data = list(map(int, input().split())) # 두번째 줄에 입력되는 N 리스트를 data에 저장
data.sort() # 입력받은 수 정렬 (오름차순)
first = data[-1] # 가장 큰 수
second = data[-2] # 두번째로 큰 수
result = 0
while True:
for i in range(k): # k번만큼
if m == 0: # 만약 m = 0이라면 반복문 탈출
break # for 문의 break
result += first # 가장 큰 수를 일단 더하기
m -= 1 # 횟수는 차감하기
if m == 0:
break # while 문의 break
result += second # 두번째로 큰 수는 한 번 더하기
m -= 1 # 횟수 차감하기
print(result)
Python
복사
# 규칙을 이용한 방법 -> 훨씬 일목요연
n,m,k = map(int, input().split())
data = list(map(int, input().split())) # 두번째 줄에 입력되는 N 리스트를 data에 저장
data.sort() # 입력받은 수 정렬 (오름차순)
first = data[-1] # 가장 큰 수
second = data[-2] # 두번째로 큰 수
# '가장 큰 수가 k번나옴 + 두번째로 큰 수가 1번 나옴' 이런 형태로 반복하면 된다.
# 따라서 동일한 형태의 반복으로 보면 (k+1)의 개수로 반복되는 것이다.
# m을 (k+1)로 나누면 반복되는 횟수가 나오고, 이 횟수에 k를 곱하면 가장 큰 수가 나온 횟수를 구하게 된다.
count = int(m / (k+1)) * k
# 나누어떨어지지 않는 경우, 남은 만큼의 횟수를 추가로 더해준다.
count += m % (k+1)
result = 0
result += count * first # 가장 큰 수가 총 나온 횟수를 더하고
result += (m - count) * second # m에서 count를 뺀 값이 두번째로 큰 수가 나온 횟수가 될 것이다.
print(result)
Python
복사
숫자 카드 게임
여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 룰은 다음과 같다.
1.
숫자가 쓰인 카드들이 N X M 형태로 놓여 있다.
2.
먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3.
그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4.
따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
•
각 행마다 가장 작은 원소를 추출하고
•
가장 작은 원소들 중에서 가장 큰 수를 출력
# 숫자 카드 게임
# 전략 : 각 행의 원소 중에서 가장 작은 값들 중 가장 큰 값에 해당하는 원소를 출력
n,m = map(int,input().split())
result = 0 # 가장 작은 음수가 아닌 값 지정
for i in range(n): # 각 행부터
data = list(map(int, input().split()))
# 행 원소 중 '가장 작은 수' 찾기
min_value = 10001 # 임의의 큰 수를 지정하고
for a in data:
min_value = min(min_value, a) # 각 행에서 가장 작은 수 추출 (반복하면서)
# 가장 작은 수들 중에서도 가장 큰 수 찾기
result = max(result, min_value) # 이전 행에서의 최댓값과 비교
print(result)
Python
복사
1이 될때까지
어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1.
N에서 1을 뺀다
2.
N을 K로 나눈다.
N과 K가 주어질 때 N 이 1이될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 알고리즘을 작성해라.
•
나의 풀이
# 1이 될 때까지
# 1. 1을 뺀다
# 2. K로 나눈다, (단 나누어떨어질때만 가능)
#### sol ####
# 2번의 방식을 최대한 많이 선택하는 것이 최소 횟수의 계산이다
# 나누어떨어져야 2번을 선택할 수 있으므로, 그 전까지는 1번을 선택하다가
# 2번을 한번 선택하면 이후부터 계속 2번만 선택한다.
n, k = map(int,input().split())
plus = 0
div = 0
while n != 1: # n이 1이 되기전까지만 수행
if n % k != 0: # 나누어 떨어지지 않으면
n -= 1
plus += 1
else: # 나누어 떨어지면
n //= k
div += 1
print(plus + div)
Python
복사
문제 : N의 범위가 10만 이하이므로 괜찮지만, 100억 이상의 큰 수가 되는 경우에도 빠르게 동작하려면, 1씩 빼주는 작업이 오래 걸린다.
•
위의 문제를 해결한 방식
N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식을 생각해볼 수 있다.
n, k = map(int, input().split())
result = 0
while True:
target = (n // k) * k
result += (n - target)
n = target
if n < k:
break
result += 1
n //= k
result += (n-1) # n이 1이 될때까지만 하면 되므로
print(result)
Python
복사