[백준 / BOJ] 12852 1로 만들기 2

문제

출처 : www.acmicpc.net/problem/12852

12852번: 1로 만들기 2

숫자 N이 주어졌을때,

1. 나누기 2

2. 나누기 3

3. 빼기 1

을 적절히 사용하여 최소한의 연산으로 1을 만드는 문제다.

 

풀이

너비우선 탐색이기때문에, 항상 최소경로가 가장 먼저나오는 BFS를 사용해 최소 연산을 찾아주면된다.

 

경로는,

의 check배열에 {연산횟수, 이전 숫자}형태로 저장해준다. 이전숫자가 없을경우(처음숫자) 이전숫자 위치에 -1을 저장해놓는다.

(연산횟수보다 작은 연산횟수가 나오지않는다면 check배열이 업데이트 되지않으므로 항상 성립한다)

배열을 따라 1부터 올라가며 경로를 찾아주고 역순으로 출력해주면 답

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/12852%201%EB%A1%9C%20%EB%A7%8C%EB%93%A4%EA%B8%B0%202/main.cpp

devxb/JJUNalgo