[dfs, dp] 백준 1463번 1로 만들기 자바 풀이

BOJ 1463번 1로 만들기 자바(java) 풀이

• 난이도: 실버3
• 백준 1463번 1로 만들기
  
  
  

문제 정리

1. 정수 X가 3으로 나누어 떨어지면, 3으로 나눈다
2. 정수 X가 2로 나누어 떨어지면, 2로 나눈다
3. 1을 뺀다
4. 위의 3가지 연산을 이용해 주어진 정수 N을 1로 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라
5. 1 <= N <= 10^6
   
   
   

문제 접근

예제를 보면 2로 나누어 떨어진다고 2로 꼭 나누어야 하는 것은 아닙니다.
2로 나눠도 되고 그냥 1을 빼도 됩니다.
예를들어 12의 경우 2로 나누어도 되고, 3으로 나누어도 되고 1을 빼도 됩니다.
즉 1빼기는 무조건 수행하고 나머지는 가능한 경우에 한해서 dfs 탐색합니다.

문제 풀이

문제 자체 분류는 DP로 분류되어 있지만 dfs에 가지치기로도 풀 수 있습니다.
우선 처음에는 가지치기를 안했다가 시간초과가 났습니다.
하지만 코드 한 줄을 넣어줌으로써 통과할 수 있었습니다.

1. 값을 입력 받습니다.
2. dfs로 재귀적 탐색을 합니다. N이 1이 될때까지 재귀 탐색합니다.
   2.1 N이 2로 나누어 떨어지면 나눈 수로 재귀 탐색합니다.
   2.2 N이 3으로 나누어 떨어지면 나눈 수로 재귀 탐색합니다.
   2.3 1을 빼서 재귀 탐색합니다.
3. N이 1이 되면 연산한 값(cnt)를 min 값과 비교하여 업데이트 합니다.
4. 시간을 더 줄이기 위해 cnt가 min 값 보다 이미 큰 상태라면 더 탐색하지 않고 return 합니다.
   
   
   

몇일 뒤에 dp방법으로 다시 풀어봐야겠다
수행속도가 빠른 풀이들은 dp를 쓴것 같아보인다.

문제 풀이

- 실행 시간: 108ms
- 메모리: 13208kb