Faits :
A.
A.a. A._ a déposé une demande de prestations (mesures médicales) auprès de l'Office AI du canton de Neuchâtel (ci-après l'office AI) le 9 avril 1997, en indiquant souffrir de naevi dès la naissance. L'office AI a pris des renseignements auprès du docteur B._, spécialiste en dermatologie et vénéréologie. Ce dernier a diagnostiqué une infirmité congénitale, à savoir des naevi multiples de grande taille, qui exposaient à trois types de complications: des problèmes esthétiques, un risque accru de mélanome et une éventuelle mélanose neuro-cutanée. Il a préconisé une surveillance clinique régulière, soit des examens de contrôle effectués chaque fois à un an d'intervalle, et un examen ophtalmologique ainsi qu'une résonance magnétique nucléaire à la recherche d'une éventuelle hyperplasie mélanocytaire intra-cérébrale (rapports des 8 mars et 24 avril 1997).
Par décision du 16 septembre 1997, l'administration a rejeté la demande de l'intéressé. Elle a considéré que le traitement relatif à l'infirmité congénitale dont souffrait A._ n'incombait pas à l'assurance-invalidité dans la mesure où les conditions fixées par le ch. 109 de l'annexe à l'ordonnance du 9 décembre 1985 concernant les infirmités congénitales n'étaient pas réunies (ci-après: OIC, RS 831.232.21; dégénérescence maligne ou excision simple impossible en raison de la grandeur ou de la localisation de l'infirmité).
A.b. L'intéressé a présenté une nouvelle demande le 29 novembre 2012. Il soutenait que, selon les derniers avis médicaux, il était inadmissible que son cas n'ait pas été pris en charge par l'assurance-invalidité dès la première demande et que les risques liés aux naevi congénitaux étaient importants. L'office AI a requis des informations auprès du docteur B._. Le médecin a confirmé le diagnostic retenu dans son rapport précédent et précisé qu'il s'agissait d'une infirmité congénitale au sens de l'OIC (rapport du 28 décembre 2012).
Se fondant sur l'appréciation du Service médical régional (SMR; avis du 6 juin 2013), l'administration a fait part à A._ de son intention de rejeter la demande (projet de décision du 21 juin 2013). L'intéressé s'y est opposé et a produit un rapport du docteur B._ daté du 17 août 2013. L'office AI a à nouveau demandé l'avis du SMR, qui est revenu sur sa position en mentionnant que vu le nombre et la grandeur de certains naevi, toute excision était impossible et par conséquent, les mesures médicales devaient être prises en charge (rapport du 10 octobre 2013). L'administration a malgré tout rejeté la demande au motif que la situation n'avait pas changé depuis 1997, que l'assurance devait prendre en charge une excision compliquée en raison de la grandeur ou de la localisation et qu'en l'occurrence il n'était pas question d'excision (décision du 7 avril 2015).
B.
Par jugement du 5 avril 2016, le Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, a admis le recours formé par A._, annulé la décision administrative et renvoyé la cause à l'intimé pour nouvelle décision au sens des considérants.
C.
L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation.
L'intéressé propose le rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit :
1.
Par le ch. 2 du dispositif du jugement entrepris, la juridiction cantonale a renvoyé la cause à l'office recourant dans le sens des considérants. Il ressort de ces derniers que le jugement entrepris ne constitue pas une décision incidente au sens de l'<ref-law>, dès lors que la juridiction cantonale a statué définitivement sur la prétention de l'intimé, le renvoi ne visant que les modalités d'exécution du droit à la mesure médicale. Il s'agit par conséquent d'un jugement final (cf. <ref-law>; 9C_684/2007 du 27 septembre 2007 consid. 1.1, in SVR 2008 IV n° 39 p. 131).
2.
Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), n'étant limité ni par les arguments de la partie recourante, ni par la motivation de l'autorité précédente. Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'<ref-law>, et ne peut aller au-delà des conclusions des parties (<ref-law>). Il fonde son raisonnement sur les faits retenus par l'autorité précédente (<ref-law>) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
3.
3.1. Est litigieux le point de savoir si l'office recourant était fondé à nier le droit de l'intimé au remboursement par l'assurance-invalidité du traitement de l'infirmité congénitale figurant au ch. 109 de l'annexe à l'OIC, tel que reconnu par la juridiction cantonale et contesté par l'administration.
3.2. Conformément à l'<ref-law>, les assurés ont droit aux mesures médicales nécessaires au traitement des infirmités congénitales - soit aux actes dont la science médicale a reconnu qu'ils sont indiqués et qu'ils tendent au but thérapeutique visé d'une manière simple et adéquate (<ref-law>) - jusqu'à l'âge de 20 ans révolus (al. 1). Le Conseil fédéral établira une liste de ces infirmités. Il pourra exclure la prise en charge du traitement d'infirmités peu importantes (al. 2). Sont réputées infirmités congénitales au sens de l'<ref-law> les infirmités présentes à la naissance accomplie de l'enfant (<ref-law>) et qui figurent dans la liste annexée à l'OIC (art. 1 al. 2 première phrase OIC). Le ch. 109 de l'annexe à l'OIC qualifie d'infirmité congénitale les "naevi congénitaux, lorsqu'ils présentent une dégénérescence maligne ou lorsqu'une simple excision n'est pas possible en raison de la grandeur ou de la localisation".
4.
La juridiction cantonale a constaté que selon l'appréciation du docteur B._ du 8 mars 1997, seuls des contrôles dermatologiques devaient être entrepris. Aucun autre traitement n'était préconisé. Une excision ne pouvait donc avoir lieu. Considérant que le texte du ch. 109 de l'OIC était clair et n'excluait pas l'intervention de l'administration lorsque l'infirmité congénitale était importante (<ref-law> a contrario), soit notamment lorsque, de par sa grandeur et sa localisation, elle ne pouvait pas être supprimée, les premiers juges ont conclu que l'office recourant aurait dû prendre en charge les contrôles et examens nécessités par l'infirmité congénitale, ou à tout le moins s'assurer par une instruction complémentaire qu'une excision n'était pas envisageable. Il en découle que l'administration aurait dû reconsidérer sa décision du 16 septembre 1997 et allouer les mesures médicales requises.
5.
5.1. L'office recourant soutient qu'en reconnaissant le droit de l'intimé à des mesures médicales au sens du ch. 109 de l'OIC, le tribunal cantonal a violé le droit fédéral. D'une part, il allègue que les contrôles dermatologiques ne tendaient pas à un but thérapeutique, comme le requiert l'<ref-law>. D'autre part, il invoque que lorsqu'une simple excision est possible, elle n'est pas à la charge de l'assurance-invalidité; en revanche, cette dernière doit prendre en charge une excision compliquée en raison de la grandeur ou de la localisation de l'infirmité. En l'occurrence, il n'était selon lui aucunement question d'excision, de sorte que l'examen de cette condition était sans objet. L'office recourant ne remet en revanche pas en discussion la possibilité de procéder à une reconsidération de la décision du 16 septembre 1997.
5.2. L'argumentation de l'administration ne peut être suivie.
5.2.1. Le fait qu'aucun traitement ni intervention chirurgicale ne soit possible n'empêche pas que les mesures médicales consistant en une surveillance clinique régulière (examens de contrôle effectués chaque année et surveillance vidéo-microscopique ainsi que par IRM; rapports du docteur B._ des 8 mars 1997 et 28 décembre 2012) soient à charge de l'assurance-invalidité. Le but thérapeutique visé en l'espèce (<ref-law>) était celui de prévenir plusieurs complications, soit notamment une transformation mélanomateuse avec éventuellement métastases cérébro-méningées ainsi qu'une méningite mélanocytaire (mélanose neuro-cutanée; rapports du docteur B._ des 8 mars 1997 et 17 août 2013). Dans la mesure où une excision n'était pas envisageable (cf. consid. 5.2.2), la mise en oeuvre d'une surveillance clinique régulière était selon le docteur B._ le seul traitement possible tendant à maîtriser l'infirmité congénitale dont souffrait l'intimé, en particulier à éviter les risques accrus de développement des maladies susmentionnées. Dans ces circonstances, un tel contrôle régulier doit être considéré comme une mesure thérapeutique et non purement prophylactique, puisqu'elle est indispensable pour pouvoir intervenir de manière adéquate en cas de transformation maligne de l'atteinte cutanée (cf. arrêts 9C_190/2013 du 23 avril 2013 consid. 2.2.3 et I 271/76 du 28 octobre 1976, in RCC 1977 p. 203).
5.2.2. Comme il ressort du jugement entrepris, il ne peut être déduit du ch. 109 de l'OIC que l'administration ne devrait intervenir que si une excision importante entre en ligne de compte. Il en résulte au contraire qu'elle n'a pas à octroyer de mesures médicales si un naevus peut être éradiqué par une simple excision. Cela n'exclut toutefois pas l'intervention de l'office recourant lorsque l'infirmité congénitale est importante (<ref-law> a contrario), soit notamment lorsque, de par sa grandeur et sa localisation, elle ne peut être supprimée par une simple excision. Une intervention chirurgicale n'est pas une condition à l'admission de l'un des cas de figure prévus par le ch. 109 de l'OIC.
En l'espèce, la question d'une éventuelle excision a été discutée par les docteurs B._ et C._ qui ont retenu qu'une telle opération était impossible (rapports des 17 août et 10 octobre 2013). Comme l'ont constaté les premiers juges, si l'administration avait procédé à une instruction complémentaire lors de la première demande de prestations, elle aurait pu obtenir la confirmation du docteur B._ que le naevus ne pouvait pas faire l'objet d'une excision dans la mesure où le médecin avait à l'époque déjà fait des propositions thérapeutiques sous la forme d'une surveillance clinique régulière, sans évoquer la possibilité d'une intervention chirurgicale ou d'un traitement (rapport du 8 mars 1997). Si l'on se réfère en outre à l'esprit de la loi, en particulier à l'<ref-law>, on comprend qu'il s'agit de refuser la prise en charge de lésions anodines. Selon les praticiens consultés, vu le nombre, la localisation et la taille des naevi, dont l'un d'entre eux - situé sur l'hémicrâne gauche de l'intimé - est considéré comme géant (vingt centimètres de diamètre), les lésions dont souffre l'intéressé ne sont pas anodines (rapports des docteurs B._ et C._ des 17 août et 10 octobre 2013).
5.3. Compte tenu de l'ensemble de ces éléments, le ch. 109 de l'OIC doit être interprété en ce sens qu'en l'espèce, les mesures médicales nécessaires à éviter une dégénérescence de l'infirmité congénitale dont souffre l'intimé devaient être prises en charge par l'office recourant. Mal fondé, le recours doit ainsi être rejeté.
6.
Vu l'issue du litige, les frais judiciaires sont mis à la charge de l'administration (art. 66 al. 1 première phrase LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties, au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, et à l'Office fédéral des assurances sociales.
Lucerne, le 5 septembre 2016
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
La Présidente : Glanzmann
La Greffière : Flury