Baekjoon 1463 1로 만들기
2019. 4. 1.
Link https://www.acmicpc.net/problem/1463 소스결과 2964KB / 0ms 출처 Baekjoon 언어 C++17 분류 다이나믹프로그래밍, BFS 설명 주어진 n을 특정 연산을 통해 1로 만드는 횟수의 최소값을 구한다. 문제 분류가 DP지만 BFS로 해결된다. 결과값이 최대 10만이기때문에 가능한것 같다. 3으로 나눈경우, 2로 나눈경우, 1 뺀 경우 3개로 나누어서 BFS를 진행한다. 알고리즘 1. n을 입력 받는다. 2. n을 Queue에 넣은 후 방문 처리한다. 3. Queue에서 원소를 꺼낸후 3으로 나눈경우, 2로 나눈경우, 1로 나눈경우를 연산하고 방문하지 않은 값이면 nextQueue에 넣는다. 4. Queue의 원소가 없다면 nextQueue의 원소를 전부 Q..
