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

P.314 만들 수 없는 금액 

내 풀이

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

maxM = max(money)

confirm = [0 for i in range(10000)]
print(confirm)
for i in range(len(money)):
    for j in range(i+1,len(money)):
        confirm[i+j] = 1

print(confirm.find(0,1))

confirm이라는 최대값까지의 0으로 찬 배열을 만들고

이중 for문을 돌아 모든 값을 더해서 그 인덱스에1을 넣어준 후에

0 인덱스를 제외한 0이 나온 첫번째 인덱스를 찾으려 했지만  잘못했다.

 

정답 풀이

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

money.sort()
target = 1

for m in money:
    if target<m:
        break
    target += m

print(target)

 

money를 sorting한 후에 

처음부터 for문을 돌면서 더 작아지면 +m을 하는 로직이다.

 

 

 

P.315 볼링공 고르기 

내 풀이

n,m = map(int,input().split())
ball = list(map(int,input().split()))
cnt=0
for i in range(0,len(ball)-1):
    for j in range(i+1,len(ball)):
        if ball[i] != ball[j]:
            cnt+=1
print(cnt)

ball을 돌며 바로 뒤에 있는 공과 비교해서 무게가 같지 않으면 그 값을 더해주기 \

테스트케이스는 전부 통과 한 것같은데 그다지 효율적이지 않았다.

 

정답풀이

n,m = map(int,input().split())
ball = list(map(int,input().split()))
cnt=0

ans=0
array = [0] * 11
for i in ball:
    array[i]+=1

for i in range(1,m+1):
    n-=array[i] #총 개수 - i무게의 공 개수 제거
    ans += array[i]*n # i무게의 공개수 * i를제외한 공 총 개수
print(ans)

일단 m 즉 공의 무게가 0~10으로 범위가 좁은걸 감안하여 인덱스에 공의 개수만큼 넣어준 후에

나름의 공식을 이용하서 풀이한 방법이다.

이렇게 풀이하면 이중 for문을 사용하지 않아도 되기 때문에 공의 개수가 무수히 많아질수록 시간복잡도가 줄어들게 된다.

 

단순히 푸는것이 아니라 효율적인 풀이를 위한 공부가 필요함을 느꼈다.

 

 

 

P.316 무지의 먹방 라이브

프로그래머스 문제로 벨로그 링크를 첨부!