Medio · voraz

Monedas mínimas

Un cajero no planifica: coge la moneda mayor que quepa, otra y otra. Esa estrategia — dar el mejor paso inmediato — es el algoritmo voraz, y con este sistema de monedas se puede demostrar que es óptimo.

En una fraseCuenta cuántas de 25 caben, luego de 10, luego de 5 y por último de 1: <code>amount / 25</code> monedas, la cantidad pasa a <code>amount % 25</code>, y así. Cuatro líneas, sin búsqueda.

El problema

Entrada: Un entero amount (1 ≤ amount ≤ 100000), los céntimos a pagar.

Salida: El número mínimo de monedas de 25, 10, 5 y 1 que suman exactamente amount.

Ejemplos:

EntradaSalida
302
999
11

El voraz no es una ley de la naturaleza: es una propiedad de este sistema de monedas. Tras la solución verás un conjunto donde la misma estrategia falla; esa es la pregunta de entrevista escondida aquí.

Tu solución

main.cpp — tu solución
Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — La división opera por lotes

amount / 25 es cuántas monedas de 25 caben de golpe — no necesitas ningún bucle sobre monedas. Tras cogerlas, lo que queda por pagar es amount % 25. Repite con 10 y con 5; lo que sobre se paga con monedas de 1, y esa última cuenta es el resto tal cual.

Pista 2 — Por qué el mayor primero es óptimo aquí

En una solución óptima hay como mucho cuatro monedas de 1 (cinco serían una de 5), como mucho una de 5 (dos son una de 10) y, cuando cabe una de 25, la mezcla 10+10+5 no ahorra nada frente a una de 25 (10+10+5 = 25). Cuenta cada denominación hasta esos topes y todo lo que quede por encima son monedas de 25: exactamente la elección voraz. La prueba es esa conta; el voraz la calcula en cuatro líneas.

Pista 3 — Sabe cuándo el voraz se rompe

Prueba la misma estrategia con monedas {4, 3, 1} y cantidad 6: el voraz coge 4+1+1 = 3 monedas, pero 3+3 bastan con 2. El voraz solo garantiza el óptimo en sistemas canónicos como 25/10/5/1. Si en una entrevista preguntan «¿funciona siempre?», ese ejemplo es la respuesta.

Solución (¡inténtalo primero!) 
#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;

    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;  amount %= 5;
    coins += amount;      // the rest is paid in 1s

    cout << coins << endl;
    return 0;
}

El voraz funciona aquí porque el sistema de monedas lo permite. Cuando no — el {4, 3, 1} de arriba, o las rarezas de las monedas reales — hay que buscar, y la mejora estándar es la programación dinámica. Antes de eso, conoce otro trueque de búsqueda por estructura: Sumas por rangos paga O(n) una vez y responde cada consulta en O(1), el mismo trato que hace el voraz.

Análisis profundo

Por qué funciona

Coge la moneda mayor que quepa y repite. Con 25/10/5/1 es demostrablemente óptimo: una solución óptima nunca necesita más de cuatro de 1, una de 5 o (cuando cabe una de 25) dos de 10 más una de 5 — así que todo lo que quede por encima de esos topes son de 25, exactamente lo que el voraz coge primero.

El coste

Cuatro divisiones y cuatro restos: O(1) de tiempo y espacio, sea cual sea la cantidad. La versión general — monedas arbitrarias, ¿se puede pagar X? — necesita programación dinámica, O(amount × monedas).

Dónde falla

  • Crees que el voraz es siempre óptimo. Con monedas {4, 3, 1} y cantidad 6 paga 4+1+1 (tres monedas) donde 3+3 gasta dos — el voraz solo es seguro en sistemas canónicos.
  • Bucle moneda a moneda (while (amount >= 25) { coins++; amount -= 25; }) en vez de dividir. Misma respuesta, pero / y % ya son ese bucle resuelto de golpe.

Siguiente paso

El trueque de pagar-una-vez-responder-muchas sigue en Sumas por rangos — prepara una vez y cada consulta es O(1).

Dos cosas para recordar

  • Voraz = el mejor paso inmediato; demuéstralo por sistema de monedas, nunca lo asumas.
  • De valor c caben amount / c de golpe; el resto es amount % c.
🐞 Esta versión falla: ábrela y pruébala

Pierde los céntimos que sobran: las de 1 no se cuentan nunca

#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;
    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;
    cout << coins << endl;
    return 0;
}