[이코테 / GREEDY] 모험가 길드

문제

# 모험가 N명, 공포도 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야

# 모험가 몇몇은 마을에 남아있어도 됨.

# 여행 떠날 수 있는 모험가 그룹 수 최댓값 구하기

입력	출력
5 2 3 1 2 2	2

 

생각

'모험가 몇몇은 마을에 남아있어도 된다'는 조건 때문에 공포도가 제일 큰 사람의 경우에 포함하려고 노력 안 하고 버려도 된다. 공포도가 큰 사람은 포함 안 시키는 방향으로 간다면, 오름차순으로 정렬해주고 공포도가 1인 사람의 경우에 혼자 갈 수 있게 해주면 되지 않을까 하는 생각이 들었다. 그래서 오름차순으로 해준 후에 어떻게 할지 고민이 컸다.

# 1번째 1, 1+2번째 2, 1+2+3번째가 3이면 그룹 하나씩 만들어질 수 있음.

# for i in range(1, n+1):

    # sum_fear = int(((i)*(i+1))/2)

    # if fear[sum_fear] == i:    

        # group += 1

이런 식으로 정렬된 배열 상태에서 1+2번째 모험가의 공포도가 2일 경우 그룹 카운트를 올려주는 식으로 하려고 했는데 저렇게 하면 sum_fear가 out of range이고 또 그렇다고 range를 조절해주자니 조건에 안 맞아서 if문으로 sum_fear <= n일 때 비교하니까 에러가 안 났다. 

((i)*(i+1))/2는 시그마n의 공식인데 sum()보다 시간 복잡도가 적게 나올 것 같아서 이 방식으로 사용했다. 그리고 얘때문에 for문 range를 1부터 시작한다. 

이론상으로 맞는데 답이 어긋나서 고민하다가 발견했다. for문은 1부터 돌지만 인덱스는 0부터 시작하기에 fear[sum_fear -1] 이렇게 1을 빼줘야 한다. 

 

몇 시간을 고민해도 안 돼서 밤새다가 그냥 자고 일어나서 샤워하다가 떠올라서 해결했다..! 될듯 말듯 해서 계속 고민했는데 시간을 너무 써서 제한 시간 넘기면 그냥 모르는 거니까 바로 확인하는 게 더 좋을지 이렇게라도 해결하는 게 좋을지...

 

코드

내 풀이

# C11. GREEDY - 기출 문제 '모험가 길드'

import sys
input = sys.stdin.readline

# 모험가 N명, 공포도 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야
# 모험가 몇몇은 마을에 남아있어도 됨.
# 여행 떠날 수 있는 모험가 그룹 수 최댓값 구하기

n = int(input())
fears = list(map(int, input().split()))

# 마을에 있어도 되는 사람의 수 제한 없음. 공포도가 큰 사람은 안 가도 되는 사람으로 빼는 방향으로...

fears.sort()

group = 0
# 공포도가 현재 그룹 사람 수로 커버 가능하면 포함하기
for i in range(1, n+1):
    # 1번째 1, 1+2번째 2, 1+2+3번째가 3이면 그룹 하나씩 만들어질 수 있음.
    sum_fear = int(((i)*(i+1))/2)    
    if sum_fear <= n:
        if fears[sum_fear - 1] == i:    
            group += 1
print(group)

 

답안 예시 참고한 풀이

# C11. GREEDY - 기출 문제 '모험가 길드'

import sys
input = sys.stdin.readline

# 모험가 N명, 공포도 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야
# 모험가 몇몇은 마을에 남아있어도 됨.
# 여행 떠날 수 있는 모험가 그룹 수 최댓값 구하기

n = int(input())
fears = list(map(int, input().split()))

# 마을에 있어도 되는 사람의 수 제한 없음. 공포도가 큰 사람은 안 가도 되는 사람으로 빼는 방향으로...

fears.sort()

group, people = 0, 0
# 공포도가 현재 그룹 사람 수로 커버 가능하면 포함하기
for fear in fears:    
    people += 1 # 이번 사람 카운팅
    if fear <= people:
        group += 1
        people = 0 # 초기화
print(group)