Faits: A. Le 18 octobre 2011, à 17h35, A._ a suivi, alors qu'il roulait sur la voie de dépassement de l'autoroute A1 (tronçon Bern/ Brünnen - Kerzers) à une vitesse de 112 km/h, sur 497 mètres le véhicule précédent à une distance de 14.58 mètres, cela représentant un intervalle de 0.47 seconde. Par ordonnance pénale du 24 janvier 2012, A._ a notamment été reconnu coupable de violation grave des règles de la circulation routière et condamné à une peine ferme de quinze jours-amende à 120 fr. le jour. Aucune opposition n'a été déposée à l'encontre de ce prononcé. Le 25 janvier 2012, le Service cantonal des automobiles et de la navigation de la République et canton de Neuchâtel (SCAN) a retiré le permis de conduire de A._ pour une durée de douze mois, retenant une faute grave de l'intéressé, ainsi que son antécédent de 2006 (retrait de sept mois pour infraction grave, purgé au 24 avril 2007). Cette décision a été confirmée le 4 septembre 2012 par le Département de la gestion du territoire de la République et canton de Neuchâtel (ci-après: le département). B. Par arrêt du 26 avril 2013, la Cour de droit public du Tribunal cantonal neuchâtelois a rejeté le recours formé par A._. Cette autorité a retenu que l'intervalle de 0.47 seconde à une vitesse de 112 km/h correspondait à peu près au quart de celui préconisé par les règles de prudence (1.8 secondes) et était donc beaucoup trop court pour permettre au conducteur de réagir en cas de nécessité. Il se situait ainsi dans la fourchette jurisprudentielle permettant de qualifier l'infraction de grave. La cour cantonale a également estimé que compte tenu de la faute et de l'antécédent de l'intéressé, la durée du retrait du permis correspondait au minimum légal. C. Par mémoire du 28 mai 2013, A._ forme un recours en matière de droit public. Il conclut à l'annulation de l'arrêt cantonal, ainsi qu'à celle des décisions du département et du SCAN, à la constatation que la faute commise est moyennement grave et, en conséquence, au prononcé d'un retrait de permis d'un mois. Le SCAN, la juridiction cantonale et l'Office fédéral des routes ont conclu au rejet du recours, sans former d'observation complémentaire. Invité à se déterminer jusqu'au 26 août 2013, le recourant n'a pas déposé de détermination supplémentaire.