[이것이 코딩테스트다 with 파이썬] 그리디

실전문제 1. 큰 수의 법칙

내 풀이

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

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

while m>0:
    for i in range (k):
        result += first
        m-=1
    result += second
    m-=1
print(result)

 

모범답안

문제 푸는 아이디어 : 반복되는 수열

반복되는 수열의 길이 = k + 1

수열이 반복되는 횟수 = m / (k + 1)

     -> m 이 나누어 떨어지지 않는 경우도 고려해야한다. m이 나누어 떨어지지 않는 경우에는 m을 k+1로 나눈 나머지만큼 가장 큰 수가 추가로 더해진다. 

 

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

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

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

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

result = 0
result += (count) * first
result += (m-count)*second

print(result)

 

 

 

실전문제2. 숫자 카드 게임

내풀이

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

arr = []

for i in range(n):    
	arr.append(list(map(int, input().split())))
## 행(가로)을 기준으로 정렬하기
for i in range(n):
    arr[i].sort

result = []
## 각 행 별 가장 작은 값을 배열에 넣기
for i in range(n):
    result.append(arr[i][0])  

result.sort

## 각 행 별 가장 작은 값 중 가장 큰 값을 출력
print(result[n-1])

 

모범답안

문제푸는 아이디어 : 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수 찾기

## min() 함수 이용하기

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

result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, intput().split()))
    # 현재 줄에서 가장 작은 수 찾기
    min_val = min(data)
    # 가장 작은 수들 중에서 가장 큰 수 찾기
    result = max(result, min_val)
   
print(result)

 

## 2중 반복문 구조 이용

n,m = map(int, input().split())
result = 0
# 한 줄씩 입력받아 확인
for i in range(n):
	data = list(map(int, input().split()))
	#현재 줄에서 가장 작은 수 찾기
	min_val = 10001
    for a in data:
    	min_val = min(min_val, a)
    #가장 작은 수들 중에서 가장 큰 수 찾기
    result = max(result, min_val)
    
print(result)

 

 

 

실전문제3. 1이 될때까지

내풀이

n, k = map(int, input().split())
result = 0
while n > 1:
    if n%k == 0:
        n /= k
        result += 1
    else:
        n -= 1
        result += 1
    
print(result)

 

 

모범답안

문제풀이 아이디어: 주어진 n에 대하여 최대한 많이 나누기

다음 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다

    1. n이 k의 배수가 될 때까지 1씩 빼기

    2. n을 k로 나누기

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

# n이 k 이상이라면 k로 계속 나누기
while n >= k:
	# n이 k로 나누어 떨어지지 않는다면 n에서 1씩 빼기
	while n % k != 0:
    	n -= 1
    	result += 1
    # k로 나누기
    n //= k
    result += 1
    
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
	n -= 1
    result += 1
    
print(result)

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

while True:
	# (n == k로 나누어떨어지는 수)가 될때까지 1씩 빼기
	target = (n // k)*k
    result += (n - target)
    n = target
    # n이 k보다 작을 때 반복문 탈출
    if n < k:
    	break
    # k로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)