Sachverhalt: A. A.a. Bei A._, geboren 1988, ist seit dem Alter von 18 Monaten eine Cerebralparese bekannt. Im Jahr 1994 wurde bei ihm ein Hirntumor (Astrozytom) operativ entfernt. Die Invalidenversicherung gewährte im Zusammenhang mit den anerkannten Geburtsgebrechen Ziff. 384 und 390 Kostengutsprache für medizinische Massnahmen. A.b. Nach seinem Lehrabbruch im Jahr 2007 meldetet sich A._ im Mai 2008 unter Hinweis auf eine psychische Erkrankung bei der IV-Stelle Bern für berufliche Massnahmen an. Diese erteilte Kostengutsprache für ein Arbeitstraining als Vorbereitung für die Weiterführung der Lehre sowie den Aufenthalt in einer Wohn- und Arbeitsgemeinschaft im Kanton B._ (Mitteilung vom 29. Dezember 2009). Im Anschluss sprach sie dem Versicherten eine erstmalige berufliche Ausbildung zum Drucktechnologen zu (Mitteilung vom 23. Juli 2010). Wegen wiederholter Verstösse gegen die Hausregeln in der Wohn- und Arbeitsgemeinschaft forderte die gestützt auf einen Delegationsauftrag zuständige IV-Stelle des Kantons Tessin A._ dazu auf, seiner Schadenminderungspflicht nachzukommen (Schreiben vom 12. August 2013). Da sich der Versicherte weiterhin nicht an die Abmachungen hielt (unter anderem wiederholter Drogenkonsum), brach die IV-Stelle Bern die beruflichen Massnahmen per 31. Oktober 2013 ab (Verfügung vom 9. Dezember 2013). Mit unangefochten gebliebener Verfügung vom 10. Februar 2014 wies die IV-Stelle das Leistungsbegehren des Versicherten wegen Verletzung der Schadenminderungspflicht ab. A.c. Am 4. September 2014 meldete sich A._ erneut zum Leistungsbezug an. Die nunmehr zuständige IV-Stelle des Kantons Graubünden gewährte ihm Kostengutsprache für das 3. und 4. Ausbildungsjahr zum Drucktechnologen EFZ (Mitteilungen vom 29. Juni und 18. August 2015). Nachdem der Versicherte die Abschlussprüfung bestanden hatte, schloss die IV-Stelle die beruflichen Massnahmen ab (Mitteilung vom 12. August 2016). Aufgrund der weiterhin bestehenden Suchtproblematik forderte sie A._ mit Schreiben vom 27. Oktober 2016 zur dreimonatigen Suchtmittelabstinenz auf, damit seine Arbeitsfähigkeit beurteilt werden könne. In der Folge veranlasste sie eine psychiatrische Begutachtung in der Swiss Medical Assessment- and Business-Center AG (SMAB). Gestützt auf die Expertise des Dr. med. C._, Facharzt für Psychiatrie und Psychotherapie, vom 4. August 2017 kündigte die IV-Stelle dem Versicherten die Abweisung seines Rentengesuchs an (Vorbescheid vom 26. Oktober 2017). Daran hielt sie mit Verfügung vom 22. Mai 2018 fest. B. Die hiergegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Graubünden mit Entscheid vom 22. Januar 2020 ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt A._ beantragen, es sei ihm in Aufhebung des angefochtenen Entscheids und der Verfügung der IV-Stelle "ab wann rechtens" eine Invalidenrente zuzusprechen. Eventualiter sei die Sache zu weiteren Abklärungen an die IV-Stelle zurückzuweisen. Zudem wird um unentgeltliche Rechtspflege ersucht. Während die IV-Stelle und die Vorinstanz auf Abweisung der Beschwerde schliessen, verzichtet das Bundesamt für Sozialversicherungen (BSV) auf eine Vernehmlassung.