[이코다] 기출문제 - 그리디

p.311 모험가 길드

내 풀이

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

guild.sort()

cnt=0
while guild:
    num = guild.pop(0)
    guild = guild[num:]
    cnt+=1

모험가 길드를 오름차순 정렬하고

quild가 없어질때까지 

첫번째 모험가를 빼고 그 모험가의 공포도만큼의 명수를  제거하면 된다고 생각했다.

 

오류 : 

2,3,3 이면 그냥 2,3이 빠지게 될텐데 3은 3명 이상이어야지 그룹이 결성될 수 있으므로 로직 자체가 틀렸다.

 

정답 풀이

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

guild.sort()

cnt=0
ans=0
for i in guild:
    cnt+=1
    if cnt >= i:
        ans+=1
        cnt=0
print(ans)

cnt : 각 그룹의 인원

ans : 그룹의 개수

 

guild를 돌며 모험가를 그룹에 넣고

모험가의 공포도 와 현재 그룹의 인원을 비교해서 그룹의 인원이 더 커지면 

그룹 모집을 마감하고 그룹 개수를 +1 증가시키는 로직이다.

 

P.312 곱하기 혹은 더하기

 

 

내 풀이

data = list(map(int,list(input())))
ans=0
for i in data:
    if i <=1:
        ans+=i
    else:
        ans*=i
print(ans)

data를 돌며 0이나 1이면 더하기를 하고

이외에는 곱하기를 하면 된다고 생각했느데 한가지 미스가 있었다.

 

바로  그때그때 ans 가 0이 될수도 있는 노릇!

그렇기 때문에 

 

정답 풀이

data = list(map(int,list(input())))
ans=0
for i in data:
    if i <=1 or ans <=1:
        ans+=i
    else:
        ans*=i
print(ans)

ans가 0과 1일때도 더할 수 있도록 고려해야 한다.

 

 

p.313 문자열 뒤집기

내 풀이

st = list(map(int,list(input())))
cnt=0
for i in range(0,len(st)-1):
    if st[i]!= st[i+1]:
        cnt+=1
print(cnt-1)

 

문자열을 받아서 단순히 변경이 되는 개수만 세면 되는걸로 착각했었는데,

정확하게 1로 바꾸는 경우와 0으로 바꾸는 경우를 계산해서 비교하는 것이 중요했다.

 

정답 풀이

st = list(map(int,list(input())))
cnt0 = cnt1 = 0

if st[0] == 1:
    cnt0+=1
else:
    cnt1+=1

for i in range(0, len(st)-1):
    if st[i] != st[i+1]:
        if st[i+1] == 1:
            cnt0+=1
        else:
            cnt1+=1

print(min(cnt0,cnt1))

 

첫번째 값을 처리한 후에 

그뒤에 값이 변경될 때마다 cnt를 해서 최소값을 구하는 풀이!