1로만들기

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 주어진 수를 아래의 연산을 반복하여 1로 만들기 1을 빼기 2로 나누기 3으로 나누기 1로 만드는 연산 횟수가 가장 적은 횟수를 출력 - 점화식 도출 int min = d[i-1] + 1; if(i % 2 == 0) { min = Math.min(min, d[i/2] + 1); } if(i % 3 == 0) { min = Math.min(min, d[i/3] + 1); } 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Mai..

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 1로 만들기 import java.util.Scanner; public class Main { // 30000까지 포함이므로 30000+1하여 선언 public static int[] d = new int[30001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); sc.close(); // 다이나믹 프로그래밍 (Bottom-up 방식) for (int i = 2; i