[백준] 11047번 : 동전0 (파이썬)

문제

나의 첫번째 답안

n,k=map(int,input().split())
a=[]
c=0
for i in range(n):
    a.append(int(input()))
    
a=list(reversed(a))

for i in range(n):
    if k>a[i]:
        c=c+k//a[i]
        k=k%a[i]
        
print(c)

reversed로 리스트를 반전해주어 사용했다. 오답이 떴다. 오름차순이라는 조건 때문인가 싶어(리스트를 변형해서 그런가) 사용하지 않기로 하였다.

나의 두번째 답안

n,k=map(int,input().split())
a=[]
c=0
for i in range(n):
    a.append(int(input()))
    
for i in range(n-1,0,-1):
    if k>a[i]:
        c=c+k//a[i]
        k=k%a[i]
        
print(c)

reversed를 사용하지 않고, 반복문을 반대로 하여서 제출하였다.
반복문 조건을 잘못 설정하였다.

나의 세번째 답안

n,k=map(int,input().split())
a=[]
c=0
for i in range(n):
    a.append(int(input()))
    
for i in range(n-1,-1,-1):
    if k>a[i]:
        c=c+k//a[i]
        k=k%a[i]
    elif k==0:
        break
print(c)

반복문 조건을 다시 설정해주고, k가 0일 때 반복문을 멈추도록 고려했다.

나의 최종 답안

n,k=map(int,input().split())
a=[]
c=0
for i in range(n):
    a.append(int(input()))
    
for i in range(n-1,-1,-1):
    if k>=a[i]:
        c+=k//a[i]
        k%=a[i]
    elif k==0:
        break
print(c)

최종답안이다.
k보다 작은 가장 큰 값을 고르면 되는 문제이다.
매번 최선의 값을 선택하는 것을 고려하여 문제를 풀면된다.(그리디)

1. 입력받는 것은 동일하다.

2. 반복문을 역순으로 돌린다.

3. 만약 k가 배열의 값보다 크거나 같다면(해당 조건을 빼먹었다.) 동전의 개수인 c는 k원으로 나눈 배열이 되고, k는 해당 배열로 나눠서 초기화를 해준다.

4. 만약 k가 0이라면 더이상 계산할 것이 없으므로 종료한다.

   • 	1) c=0+4790//1000=>4(동전 4개), k=4790%1000=790
     	2) c=4+790//500=>4+1(동전 5개), k=790%500=290
     	3) c=5+290//100=>5+2(동전 7개), k=290%100=90
     	4) c=7+90//50=>7+1(동전 8개), k=90%50=40
     	5) c=7+40//10=>8+4(동전 12개), k=40%10=0(종료)

오늘의 반성

이렇게 많이 틀린 날은 많은 반성을 하게 된다.
몰라서 틀린거면 공부하면 되지만, 오늘처럼 문제 조건을 제대로 챙기지 않아 틀리는 날은 진짜 반성해야 된다... 알면서 틀리는게 제일 바보같은거다ㅠ
또한 그리디 알고리즘을 풀기 시작했으므로 메모리나 시간초과 등에도 신경써야겠다는 생각이 든다.
문제 조건 놓치지말고 하나하나 정리하면서 풀어보는 연습을 해야겠다.