f20 에서 f15 + 1은 이해가 됩니다...
다만, f15 에서 f10 +1 +1 / f12 +1 +1 은 이해가 되지 않습니다.
15원을 만들기 위해서는 10원을 만든 동전 개수에서 5원짜리 동전+1 만 하는게 맞지 않나요?
마찬가지로 f12도 12원을 만들기 위해서는 12원을 만든 동전개수에 3원짜리 +1만 하면 되는줄 알았지만 왜 f10 +1+1 / f12+1+1 인지 이해가 되지않습니다...
답변 1
1
안녕하세요 푸푸님.
주어진 문제에 따르면 3원, 5원짜리 동전이 존재합니다.
따라서, 20원을 지불하기 위해서는 15원을 지불한 뒤 5원을 추가로 사용하거나, 17원을 지불한 뒤 3원을 추가 지불하는 방법이 있습니다.
fn을 n원을 지불하기 위해 사용한 동전의 총 수라고 할 때, 위 내용을 수식으로 나타내면 아래와 같습니다.
f20 = min(f15+1, f17+1) ......(1)
여기서, f15와 f17은 base case가 아니기 때문에, 같은 방식으로 표현이 가능합니다.
f15 = min(f10+1, f12+1) ......(2)
f17 = min(f12+1, f14+1) ......(3)
여기서, 2를 1에 대입하면 아래와 같은 식이 나옵니다.
f20 = min( min(f10+1, f12+1)+1, f17+1)
말씀해주신 수식
f10+1+1, f12+1+1은 위와 같은 계산 과정에서 유도된 것으로 생각됩니다.
푸푸님이 만족하시는 답변이 되었기를 바라며, 답변 해결로 상태 변경을 부탁드립니다.
이후에도 문제를 풀거나 공부하시면서 어려운 점이 있다면 질문 올려주세요.
감사합니다.
26년2회 실기기출은 언제쯤...
0
4
1
재귀함수 종료조건
0
4
1
이론 공부법 요약본 버전 업데이트 문의
0
13
1
백준 서비스 종료로 인한 강의 자료 업데이트 요청드립니다.
0
21
1
백준 사이트 준비중이라 문제를 볼 수 가 없어요
0
20
1
코딩살구클럽 가입부탁드립니다
0
25
2
동전문제 풀이 질문
0
111
2
장기문제 최종 cpp파일
0
169
2
이해가 안되는 부분이 있습니다.
0
349
1
배낭문제가 백준문제로 있어서 작성했는데 왜 안되는지 알 수 있을까요?
0
524
1
혹시 이건 왜 안되는지 말씀해주실 수 있나요??
1
567
2
코딩테스트 공부법에 대한 질문
0
649
1
입력함수 출력함수 관련
0
441
1
강의자료
0
1212
1
동전구현문제
0
376
1
아파트 단지 문제
0
340
2
DFS
0
432
1
수업하신 PPT 자료는 다운 못하나요?
0
376
1
C언어로 푼 코드는 없나요?
0
350
1
안녕하세요! 왜 +1 을 하는 지 모르겠습니다
0
239
1
DFS함수 동작 원리 강의 14분 33초 호출 스택 관련 질문
0
234
1
코드를 무조건 짧게하는게 좋은건가요?
1
407
1
이해한게 맞는지 잘 모르겠습니다
1
284
1
모범 답안
0
395
1