[Python] 백준 11047 동전0

백준 11047

 

N,K=map(int,input().split())

some_list=[]
for i in range(N):
  some_list.append(int(input()))

count=0
while(K>0):
  for i in range(N-1,-1,-1): # 리스트 맨 뒤 인덱스부터
    if(K-some_list[i]>=0): # K값에서 리스트 값을 뺏을 때 0보다 크거나 같음
      K=K-some_list[i]  # K값 감소
      count=count+1
      break
    else: #크다면 리스트 인덱스 줄여주기 위해 N값 감소 -1
      N=N-1 

print(count)

 

 

 

처음에는 1<=Ai<=1,000,000 , A1=1, i>=2 인 경우에 Ai는 Ai-1의 배수라는 조건을 고려하지

않고 코드를 작성했다.  리스트 맨 뒤 인덱스부터 시작하여, K값에서 리스트 값을 뺐을 경우

0보다 크거나 같을 경우 count 하고,  크다면 for문에서 검사하는 리스트 인덱스를 줄여주기 위해

N값을 감소시켜주는 방향으로 코드를 작성했다. 

 

 

 

그 결과 시간초과가 발생하였다. 

시간초과

 

 

 

 

 

 

#문제조건을 고려해서 작성한 코드 

N,K=map(int,input().split())

some_list=[]

for i in range(N):
  some_list.append(int(input()))

count=0

for i in range(N-1,-1,-1): 
  count=count+K//some_list[i] #카운트 값에 K를 동전으로 나눈 몫을 더해준다

  K=K%some_list[i] # K는 동전으로 나눈 나머지 값으로 반복한다.


print(count)

 

 

 

 

문제의 조건&amp;amp;nbsp;

 

 

 

이 문제의 조건을 생각해 본다면, 큰 동전이 전부, 작은 동전의 배수가 된다는 뜻이였다. 이러한 조건이 있기에, 그리드 알고리즘을 적용했다. 

 

리스트의 맨 뒤 인덱스(가장 큰 동전)부터 시작하여, K를 동전으로 나눈 몫을 더해주기 시작한다.  K값은 동전으로 나눈 나머지 값으로 계속해서 반복해주면 된다. 

만약(K값이 동전의 값보다 작다면 나눈 몫은 어차피 0 이므로 고려하지 않아도 된다)