[알고리즘]백준 11047번 동전0
문제
https://www.acmicpc.net/problem/11047
전략과 후기
그리디 알고리즘은 매 순간마다 가장 유리한 경우를 선택하는 방식으로 풀어야 한다. -> 동적계획법과 비교됨
-> M보다 가치가 작은 동전 중 가장 큰 가치값을 가진 동전으로 빼는 전략
- 처음 풀때 너무 단순히 생각하고 풀었다 -> 그냥 뺼샘 여러번 -> 몫이랑 나머지 생각못함 (시간초과뜨고나서 알음) -> 뺄셈여러번은 나눗셈으로 한번에 할 수있다라는 생각을해야지!! 덧셈과 곱셈도 마찬가지일테고~
- M이 모든 동전의 가치보다 클경우를 첨에 고려안했었음 -> 런타임에러 -> 질문검색에서 찾아서 꺠달았지 안그랬으면 몰랐을듯
쉬운문제도 두번보자.
예제의 입력값 외의 경우 반드시 고려
꼭 생각!!!! 예제 입력값은 일부러 좁은 입력값 범위만 제공해줄 가능성이큼! 보통 극한의 경우 완전 입력값이 적을떄, 많을떄, 여사건의 경우를 생각하는게 좋다.
코드
import sys
inputNM= sys.stdin.readline().split(" ")
N=int(inputNM[0])
M=int(inputNM[1])
inputLs= []
for i in range(N):
inputNum = int(sys.stdin.readline())
inputLs.append(inputNum)
for i in range(N):
if inputLs[i] > M:
index = i-1
break
elif i == N-1:
index = N-1
count =0
while M >0 :
if inputLs[index] > M:
while inputLs[index] >M:
index-=1
divider = M// inputLs[index]
M-= divider * inputLs[index]
count+=divider
print(count)
Author And Source
이 문제에 관하여([알고리즘]백준 11047번 동전0), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@wjdxor6346/알고리즘백준-11047번-동전0
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
inputNM= sys.stdin.readline().split(" ")
N=int(inputNM[0])
M=int(inputNM[1])
inputLs= []
for i in range(N):
inputNum = int(sys.stdin.readline())
inputLs.append(inputNum)
for i in range(N):
if inputLs[i] > M:
index = i-1
break
elif i == N-1:
index = N-1
count =0
while M >0 :
if inputLs[index] > M:
while inputLs[index] >M:
index-=1
divider = M// inputLs[index]
M-= divider * inputLs[index]
count+=divider
print(count)
Author And Source
이 문제에 관하여([알고리즘]백준 11047번 동전0), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wjdxor6346/알고리즘백준-11047번-동전0저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)