[BOJ #30892] 상어 키우기

문제

인천대학교의 앞바다에는 N마리의 상어가 살고 있다고 한다. 각각의 상어는 서로 같거나 다른 크기의 몸집 A_i를 가지고 있다. 상어의 세계는 완전한 약육강식의 세계로, 상어 자신의 크기보다 작은 상어는 전부 먹을 수 있다. 이때, 상어의 크기는 잡아먹힌 상어의 크기만큼 커지게 된다. 반면, 자신의 크기 이상인 상어는 전혀 잡아먹지 못한다.

어느 날 크기가 T인 샼이라는 이름의 아기 상어는 인천대학교 앞바다에 존재하는 N마리 상어들의 크기 정보를 모두 입수했다. 똑똑한 아기 상어 샼은 인천대학교 앞바다에 있는 상어들을 최대 K마리까지 적절한 순서로 잡아먹고, 자신의 몸집을 최대로 키울 계획을 하고 있다.

샼이 최선의 선택으로 최대 K마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 구해보자.

 

입력

첫째 줄에 인천대학교 앞바다에 존재하는 상어의 마릿수 N과, 샼이 먹을 수 있는 상어의 최대 마릿수 K, 샼의 최초 크기를 나타내는 정수 T가 공백으로 구분되어 주어진다. (1 ≤ K ≤ N ≤ 200,000, 1 ≤ T ≤ 10^9)

둘째 줄에는 인천대학교 앞바다에 존재하는 N마리의 상어 크기를 나타내는 정수 A_i가 각각 공백으로 구분되어 주어진다. (1 ≤ A_i ≤ 10^9)

 

출력

샼이 최선의 선택으로 최대 K마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

 

내가 쓴 코드 1 (틀림)

# 재귀
import sys; input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# N : 상어 수, K : 먹을 수 있는 최대 수, T : 상어 최초 크기
N, K, T = map(int, input().split())
shark_sizes = list(map(int, input().split()))
# 큰 애들 부터 가져오기
shark_sizes.sort(reverse=True)

# 자신의 크기보다 작은 상어만 먹 가능

def growing(size):
    global cnt, ans
    if cnt == K:
        ans = size
        return

    for i in range(len(shark_sizes)):
        if shark_sizes[i] < size:
            size += shark_sizes[i]
            shark_sizes.pop(i)
            cnt += 1
            growing(size)
            return

cnt = 0     # 먹은 수
ans = 0
growing(T)

if ans == 0:
    ans = T
print(ans)

 

내가 쓴 코드 2 (..?)

# while-for문
from sys import stdin; input = stdin.readline
# N : 상어 수, K : 먹을 수 있는 최대 수, T : 상어 최초 크기
N, K, T = map(int, input().split())
shark_sizes = list(map(int, input().split()))
# 큰 애들 부터 가져오기
shark_sizes.sort(reverse=True)

# 자신의 크기보다 작은 상어만 먹 가능
cnt = 0
while True:
    if cnt == K:
        break
    for i in range(len(shark_sizes)):
        if shark_sizes[i] < T:
            T += shark_sizes[i]
            shark_sizes.pop(i)
            cnt += 1
            break
    else:
        break

print(T)

위의 코드에서 재귀를 빼서 작성한 코드....

이거 제출할 때마다 결과가 다르다.. 모지? 이거랑 비슷한 코드가 맞은 경우가 있길래 한 번 똑같이 제출해봤는데, 저번엔 시간 초과 떴던 게 이번엔 맞았다..?? 그래서 제한 시간을 수정해놓으셨나 했는데, 또 다시 제출하니까 이번엔 또 시간 초과다...???? 모지용?

 

내가 쓴 코드 3 (맞.)

# while문
from sys import stdin; input = stdin.readline
# N : 상어 수, K : 먹을 수 있는 최대 수, T : 상어 최초 크기
N, K, T = map(int, input().split())
shark_sizes = list(map(int, input().split()))
# 큰 애들 부터 가져오기
shark_sizes.sort(reverse=True)
# 자신의 크기보다 작은 상어만 먹 가능
cnt = 0
small = []
while cnt < K:
    if shark_sizes and shark_sizes[-1] < T:
        small.append(shark_sizes.pop())
    else:
        if small:
            T += small.pop()
            cnt += 1
        else:
            break
print(T)

다른 사람 코드 참고해성... 진짜 똑똑한 코드... 똑똑한 사람...ㅎㅎ

내가 스택 문제 풀고 싶어서 골랐던 문젠데, 생각보다 안풀렸다.. 시간 제한 때문에 더 어려웠던듯..! 문제 생긴지도 얼마 안돼서 정답 코드도 잘 없었음 힛!

 

제출 결과