가장 큰 값을 뺴는 이유가 궁금합니다.
309
작성한 질문수 44
예를 들어서 1 2 5 로 7원을 거슬러줄때 dp[6] 이나 dp[5]가 아닌 dp[2] 에서 1을 더한값과 비교하는 것은 dp[5] dp[6]에서 더해줄 경우 1 + 2 + 5 + 1 과 같이 2개의 동전이 겹치는 경우가 발생하는 반면 dp[2]에서 더해줄 경우 매 순간마다 오름차순 덧셈으로 정렬이 되어서 겹치는 것을 방지 할수 있기에 최적의 해임을 보장받기 때문인가요????
답변 1
0
안녕하세요^^
7원을 만들기 위해 5원을 하나 사용한다는 전제하에서 7원에서 5원을 빼고 남은 2원을 만드는데 사용되는 동전의 최소 개수가 dp[2]에 있으니 dp[2]+1(5원 1개 사용) 를 해서 기존 dp[7](7원을 만드는데 사용된 동전의 최소개수)값보다 작으면 바꿔주는 것입니다.
안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.
0
70
2
갑자기 채점 사이트가 바뀌었어요
0
50
1
문제 리스트 페이지
0
41
1
채점 사이트 관련 질문드립니다
0
39
1
봉우리 문제 질문입니다
0
102
2
씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?
0
72
0
이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?
0
78
0
가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법
0
76
1
좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ
0
94
2
6-7 강의에서
0
53
1
6-6. 장난꾸러기 질문 있습니다.
0
50
1
강의 수강후 코딩테스트
0
124
1
answer 변수 사용 여부
0
50
1
2중 for문
1
96
2
2-11. 임시반장정하기 (Runtime Error)
0
67
1
혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?
0
75
1
이런 풀이는 어떨까요
0
50
1
자바 스트림 방식의 효율성 질문 드립니다.
0
62
1
알고리즘 자료 구조들..
0
68
1
StringBuilder vs BufferdWriter
0
52
1
원더랜드(프림)
0
55
1
이런 코드는 어떤가요?
0
66
1
bfs 풀이
0
61
1
병합정렬
0
58
1