방법 수와 최소 개수를 다른 표로 풀어요

오늘의 질문

저금통을 채우는 모든 방법을 세는 대신 가장 적은 동전으로 채운 영수증만 남기는 것과 같아요.

아직 답을 몰라도 괜찮아요. 아래 작은 예시를 보고 먼저 예상해 보세요.

왜 배우는지 쉬운 설명 보기

“방법 수와 최소 개수를 다른 표로 풀어요”에서 무엇을 먼저 알아야 할까요?

01 · 혼자 확인해요

연습한 문제를 다시 풀며 혼자 확인하기

지금은 방금 연습한 문제를 다시 보는 시간이에요.아직 “완전히 익혔다”고 기록하지 않아요. 나중에 모양이 다른 문제도 도움 없이 풀면 그때 다시 확인할 수 있어요.

선생님과 검토자가 보는 확인 기준처음 풀 때는 이 숫자를 몰라도 괜찮아요.

답과 과정 확인: 80% 이상
내 말로 설명: 80% 이상
막힌 곳 고치기: 80% 이상
다른 문제에 써보기: 80% 이상

스스로 확인하며 작성 중인 답0 / 4

01
먼저 생각하기 · 기초
dp29-predict: 목표 금액의 최소 동전 수에서 dp[x]는 금액 x를 정확히 만들 때 필요한 최소 동전 수이며 불가능하면 ∞다. dp[0]=0에서 각 금액과 동전에 대해 도달 가능한 dp[x-coin]+1의 최소값을 취한다.
지금은 답을 먼저 보여 주지 않아요. 내가 적은 답은 연습 메모로만 저장되고, 합격으로 기록되지 않아요.
혼자 고른 답과 까닭 한 줄완벽하지 않아도 괜찮아요. 내 생각을 짧은 한 문장으로 적어 보세요.
연습과 같은 문제를 다시 풀어 보는 시간이에요. 힌트 없이 먼저 생각해 보세요. 지금 적은 답은 바로 합격으로 기록되지 않아요.
정답과 비교

한꺼번에 여덟 문제를 펼치지 않아요. 내 생각을 적고 맞춰 볼 기준을 확인하면 다음 문제 하나만 열립니다.

4개 답이 남았습니다.

02 · 나중에 한 번 더

모양이 다른 문제에서도 같은 생각을 써봐요

도움을 보지 않고 새 그림에서도 “방법 수와 최소 개수를 다른 표로 풀어요” 규칙을 한 번 골라 보세요. 무엇이 먼저 달라지는지 말해 보세요.

혼자 확인하기

처음 보는 비슷한 문제를 도움 없이 다시 풀고, 달라진 첫 지점을 내 말로 설명해 보세요.

혼자 해냈다고 볼 기준 보기선생님이나 검토자와 결과를 확인할 때 사용할 기준이에요.

dp29 목표 금액의 최소 동전 수의 미공개 empty·singleton·tie-heavy·state-collision·unreachable·cycle·overflow·scale fixture에서 AI 없이 state meaning·two-history sufficiency·base·recurrence·dependency order·independent optimum·parent witness·cost·human verdict를 작성하고 deterministic replay evidence를 제출한다.

AI가 제안한 목표 금액의 최소 동전 수 설명에 missing state dimension·value-is-state·unreachable-is-zero·cache-is-polynomial·recurrence-is-proof·wrong in-place loop·unsafe sentinel·missing parent tie·pseudo-polynomial-is-polynomial·optimization-without-premise 중 하나 이상을 심어 공식 source와 candidate를 공유하지 않는 작은 oracle로 찾아 수정한다.