백준 No.1463 1로 만들기 - JAVA

 

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세가지이다.

- X가 3으로 나누어 떨어지면, 3으로 나눈다.

- X가 2로 나누어 떨어지면, 2로 나눈다.

- 1을 뺀다.

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력

 

 

풀이

3으로 나누거나, 2로 나누거나, 1을 빼서 연산 횟수의 최솟값을 구하는 문제이다.

여기서 배열(arr- DP) 배열의 인덱스는 주어진 숫자를 뜻한다. 즉 arr[10] 이면 10을 만들 때 사용한 연산 횟수의 최솟값이다. 그래서 아래와 같은 3가지 경우가 나올 수 있다.

 

3으로 나누어 떨어진다 -> arr[N/3]

2로 나누어 떨어진다 -> arr[N/2]

1을 뺀다 -> arr[N-1]

 

그리고 어떤 값이 주어지던 arr[0], arr[1] 은 구할 필요가 없기에 0으로 계산되고, arr[2], arr[3] 은 1로 지정된다. 그러면서 이 값들로 계산해 나가면서 답을 구한다. DP 문제이다. 그리고 이 값들을 바로 대입하기 위해 1을 뺀 값을 반복문 첫번째 부분에서 바로 구한다 

 

단계별 풀이

.

ar은 DP 배열이고 여기서 arr[2] 라고 예시를 들면 arr[2] = arr[1] + 1; 로 볼 수 있다. 2가 1이 되려면 2-1 = 1 로 계산 할 수 있다. 결국 횟수는 한 번이다. 그렇다면 1이 1이되는 횟수는 몇일까?

1이 1이 되는 횟수는 1이다. 결국 (주어진 수 : 2) = (주어진 수 -1 : 1) +1;  결국 자신의 바로 이전 순서에 횟수 +  1 이 자신의 연산 최소 횟수가 된다. 

근데 이 경우는 2와 3으로 주어진 수가 나뉘어지지 않을 경우 이야기이고 만약 나뉘어질 경우

-1 한 값과 2 또는 3으로 나뉘어진 값에서 최솟값을 찾아야 한다. 결국 Math.min을 사용하여 계산해야 하는 문제이다.

 

디버깅 결과 N이 10이 주어진 경우

이런식으로 계속 진행된다 그러다 결국

이런식으로 채워지며 arr[10] 에는 최소 연산횟수가 들어있는 걸 볼 수 있다. 이렇게  전에 구한 값을 통해 뒤에 값을 빠르게 구하는 DP 문제였다.

 

 

코드

 

 

개념적 참고를 한 블로그

https://uncertainty.oopy.io/boj/class-problem-solving/make-it-1

[1463번] 1로 만들기