✓

태그:

26. 동적 계획법과 최단거리 역추적 CLASS 5 ESSENTIAL

1에서 시작하여 i를 늘려가면서 i까지의 최소 횟수를 계속 구하면 될 것 같아요…!!

풀이 비스무리한거 보기

주어진 연산을 여러 번 취하여 n을 1로 만드는 방법의 최소 연산 횟수와 그 과정을 출력하는 문제입니다. 사용할 수 있는 연산은 3으로 나누어질 때 3으로 나누기, 2로 나누어질 때 2로 나누기, 그리고 1로 빼기입니다. 개인 취향 차이가 있을 수 있겠지만, 크게 2가지 풀이가 가능합니다. 먼저, n에서 시작해서 가능한 연산을 여러 번 사용하여 1로 만드는 방법, 그리고 1에서 시작해서 n으로 가는 최단 거리를 찾는 방법입니다.

첫 번째는 BFS를 사용할 수 있는데, n을 큐에 집어넣고 가능한 연산을 모두 취하여 방문하지 않은 숫자만 계속 연산을 진행하면 됩니다. 두 번째는 1부터 시작하여 1을 더한 값, 2를 곱한 값, 3을 곱한 값을 모두 탐색하여 거꾸로 최소 횟수를 유지하면서 n으로 가는 경로를 찾으면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-22 23:05:35

---