1로 만들기
📌문제정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음 4가지이다.1. X가 5로 나누어 떨어지면, 5로 나눈다.2. X가 3으로 나누어 떨어지면, 3으로 나눈다.3. X가 2로 나누어 떨어지면, 2로 나눈다.4. X에서 1을 뺀다. 정수 X가 주어졌을 때 연산 4개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 📌풀이만약 x=6일 때f(6) -> f(5), f(3), f(2) f(5) -> f(4), f(1)f(3) -> f(2), f(1)f(2) -> f(1), f(1)같은 함수들이 동일하게 여러번 호출되고 있으므로 다이나믹 프로그래밍으로 해결 📌코드x = int(input())# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화d = [0] ..
코딩테스트
2024. 10. 29. 18:42