BJ 1463

[BJ] 백준 11463 1로 만들기(JAVA)

문제 https://www.acmicpc.net/problem/1463 풀이 방법 문제는 간단하다. 1. x가 3으로 나누어떨어지면, 3으로 나누기 2. x가 2로 나우어 떨어지면, 2로 나누기 3. 1를 빼기 위 세개의 연산을 적절히 사용해서 1을 만드는데 연산을 사용하는 횟수의 최소값을 구하는 문제이다. 이 문제는 dp를 사용해서 풀면 된다. dp[N]에는 N이 1이 될때까지의 최소 연산 횟수를 가지고 있다. 우선 N이 2또는 3으로 나누어떨어지는지 확인한다. 만약 나누어 떨어진다면 2로 나눴을 때와 3으로 나눴을때 어떤 수가 더 최소연산 횟수를 가지는지 비교해서 더 작은 값을 dp에 넣는다. 그리고 항상 -1를 했을 경우의 연산의 최소값을 구해서 기존의 dp값과 비교 후, 더 작은 값을 dp에 넣어..