Baekjoon 1463 1로 만들기 JAVA

해당 문제는 처음에는 쉬울 거라 생각했는데 문제를 풀다 보니 DP를 이용해야 하는 문제인 걸 알게 되었고 이제 일련의 답을 나열해가면서 특정 관계를 찾을 수 있었다.

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

DP ver

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201463

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

BFS ver

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201463%20BFS

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

​

해당 문제는 입력받은 정수를 1로 만드는 과정에서 최소 횟수를 구하는 문제이다.

조건

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

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

1을 뺀다.

해당 조건을 이용해 최솟값을 출력하면 된다.

​

처음에는 그냥 if 문을 통해 3이나 2로 나눠지면 나누고 아니면 1을 빼고 이런 식으로 문제를 해결했더니 생각해 보니 최솟값을 비교하지 않고 하나의 값만 출력되는 걸 확인했고 이에 어떻게 할지 고민하다 구글의 힘을 빌려 DP를 사용해야 하는 것을 알게 되었다.

​

1 : 1로 만들어졌으니 횟수 0

2 : 2로 나누면 1이니 횟수 1

3 : 3으로 나누면 1이니 횟수 1

4 : 2로 나누면 2, 2로 나누면 1이니 횟수 2

5 : 1을 빼주면 4, 2로 나누면 2, 2로 나누면 1이니 횟수 3

6: 3으로 나누면 2, 2로 나누면 1이니 횟수 2 or 2로 나누면 3, 3으로 나누면 1이니 횟수 2

7 : 1을 빼주면 6, 3으로 나누면 2, 2로 나누면 1이니 횟수 2 or 1을 빼주고, 2로 나누면 3, 3으로 나누면 1이니 횟수 2

8 : 2로 나누면 4 , 2로 나누면 2, 2로 나누면 1이니 횟수 3

9 : 3으로 나누면 3, 3으로 나누면 1이니 횟수 2

10: 2로나 누면 5, 1을 빼주고, 2로 나누면 2, 2로 나누면 1이니 횟수 4 or 1을 빼주면 9, 3으로 나누면 3, 3으로 나누면 1이니 횟수 3

이런 식인 것 을 확인할 수 있다.

​

여기서 보면 4는 2로 나눈 횟수에서 2의 횟수를 더하면 되고 5는 1을 빼준 횟수에 4의 횟수를 더해주면 되고 8의 경우 2로 나눈 횟수에 4를 더해주면 된다.

​

이를 토대로 2로 나눠질 경우 2로 나눈 몫에 해당하는 횟수에 +1을 한 것과 1을 뺀 수에 해당하는 횟수에 +1을 한 것과 비교하여 더 작은 수를 저장해 주고 3으로 나눠질 경우 3으로 나눈 몫에 해당하는 횟수에 +1을 한 것과 1을 뺀 수에 해당하는 횟수에 +1을 한 것과 비교하여 더 작은 수를 저장해 준다.

이때 if 문과 else if 문이 아닌 둘 다 if 문으로 비교하여야 최솟값을 찾아낼 수 있다.

​

2021.09.14 (추가) 해당 문제를 다시 풀어보았는데 이번엔 dp뿐만 아니라 bfs로도 가능할 거 같아서

한번 풀어보았다. 문제는 해결했는데 역시 dp가 더 빠르다.