코딩스토리

백준 12852번 - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이 문제는 BFS, 다이나믹 프로그래밍 문제이다. 처음에는 top-down 방식으로 문제를 해결하려 했다. 문제의 조건에 맞게 코드를 짜 보았는데 마지막 출력에서 살짝 맘에 안 들었다. 출력 부분을 보면 n부터 내림차순으로 출력하는데, top-down 방식으로 해결하려면 dp[x]에는 x*3 또는 x*2 또는 x+1 이 들어가 있기 때문에 한번 vector나 배열에 다 넣고 오름차순 정렬을 해줘야 한다. 코드는 몇 줄 차이 안 나겠지만 시간 복잡도 면에서 botto..