배운점
1.배열 -인덱스에 접근을 막기위해 if를 씀.
2.greedy, dp 둘다 알자.
서론
학교 수업에서 동전문제가 나왔습니다.
당연히 greedy겠구나 하고 풀고
별 생각 없었는데
1, 3, 4원일때 greedy가 실패함을 보게 되었습니다.
충격을 받고, dp 동전문제를 파보았습니다.
//참고
n을 이루는 최소 동전 갯수 문제입니다.
본론
재귀도 있지만, 보통 안쓰는 분위기니
1.for문과
2.사용한 최적 동전 수열 구하기
3. 경우의 수 모든 수열 구하기
이 3개가 메인인듯 보였고, 이를 조금 써보자 합니다.
풀 코딩은 손코딩으로 실컷 했기에 요점만 쓰겠습니다.
1 요점.
for 1~ N
i = MAX
for (coin : coins)
if( i - coin >= 0)
min(dp[i], dp[i-coin] +1
dp[n] 출력
2. 1의 과정에서 min의 조건을 if로 올리고
min바로밑에 first로 그 coin을 저장.
while(n>0)
arr.add(first (N))
N- FIRST(N)
arr출력
//휴대폰으로 쓰는게 상당히 힘들군요..
3.2중for문에
count( x )+= count (x-coin)
로 구하면 됩니다.
마무리
이를 공부하고 고민하며 손코딩한 사진들 올리며 마무리 하겠습니다.



'알고리즘' 카테고리의 다른 글
| [알고리즘 - java] 1700 멀티탭 스케줄링 (1) | 2025.07.08 |
|---|---|
| [알고리즘 - java] 1194 달이 차오른다, 가자 (0) | 2025.05.07 |
| [알고리즘-java] 부분수열 (문제는 없음) (0) | 2025.03.22 |
| [알고리즘-java] 1339 단어 수학 (0) | 2025.03.06 |
| [알고리즘-java] 12100 2048 (Easy) (0) | 2025.03.04 |