백준 12852번 1로 만들기 2

문제 링크입니다: https://www.acmicpc.net/problem/12852

 

연산을 하는 횟수의 최솟값은 DP를 통해 간단하게 구할 수 있는 문제였습니다.

문제는 " N을 1로 만드는 방법에 포함되어 있는 수"를 출력하는 것이었는데 이는 DP에 사용했던 cache 배열을 역추적하며 구할 수 있었습니다.

테스트해 본 결과 top-down 방식으로 구현할 경우 N이 100만 일 때 stackoverflow가 발생하는 것 같은데 AC를 받는 것으로 보아 데이터 추가가 필요해 보입니다.

 

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~