주어진 수에 /3, /2, -1을 사용해 최소횟수로 1을 만드는 프로그램 탑다운(재귀)방식으로 작성. 메모리제이션을 위한 배열 D[]를 만든다. 주어진 수를 쪼개어 작은 수(x-1, x/2, x/3)로 만들고, 작은 수들에 대해 세 가지 방법 중 최소횟수인 방법을 찾아 배열에 저장한다. x=1일 때, 재귀에서 빠져나온다. import java.util.Scanner; public class BOJ1463 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int x=sc.nextInt(); int[] D=new int[1000001]; System.out.println(operate(x, D)); } static in..
Coding Test(Algorithms)
n자리의 이진수 중 1이 연속하지 않는 수인 이친수의 갯수를 구하기 - d[n+1][3]짜리 배열을 생성, n의 최댓값 90일 때 int의 범위를 넘어가므로 long타입으로 지정한다. - d[i][j]: i자리의 이진수 중 j로 끝나는 이친수의 갯수 - i자리이고 1로 끝나는 이친수의 갯수는, i-1자리이고 0으로 끝나는 이친수의 갯수와 같다. - i자리이고 0로 끝나는 이친수의 갯수는, i-1자리이고 0, 1로 끝나는 이친수의 갯수와 같다. - 즉, d[i][1]=d[i-1][0], d[i][1]=d[i-1][0]+d[i-1][1] 이다. - 한자리 수인 이친수는 1뿐이므로, 1로 예외처리하여 저장한다. import java.util.Scanner; public class BOJ2193 { public..
주어진 수열에서 연속하는 수를 합쳤을 때의 최대값 구하기 - i개의 수를 가진 수열 a[], 인덱스 i까지의 수 중 a[i]와 연속한 수를 합한 최대값을 d[]에 저장함 - d[i]: a[i]와 연속한 수들의 합 중에서 최대값 - 즉, d[i]는 i-1까지의 연속한 수들의 합 중 최대값에서 a[i]를 더할지 말지 선택하여 나온 결과이다. - d[]를 구한 뒤, 저장된 수 중 최대값을 고르면 정답. import java.util.Scanner; public class BOJ1912 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n + 1];..
1,2,3의 합으로 주어진 수를 표현하는 방법 출력하기 주어진 수가 1,2,3일 때, 각각의 반환값 1,2,4를 저장한다. 덧셈으로 표현될 때 마지막 더해지는 수가 1,2,3인 경우를 생각하여 d[x]=d[x-1]+d[x-2]+d[x-3] 을 작성한다. import java.util.Scanner; public class BOJ9095 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t-- > 0) { int n = sc.nextInt(); int[] d = new int[n + 1]; System.out.println(operate(n, d)); } } st..
n자리 수 중 각 자리 숫자가 연속하는 수인 계단수의 갯수를 출력하기 - d[n+1][10]짜리 배열을 생성하여 메모이제이션 - d[i][j]: i자리수의 수 이면서, 가장 끝자리(일의 자리) 숫자가 j인 계단수의 갯수 - n=1일때, 예외처리로 d[1][1]~d[1][9]에 모두 1을 저장함 - i자리 수이면서 j로 끝나는 계단수는, i-1자리 수이면서 j의 연속하는 수인 j-1, j+1으로 끝나는 계단수의 합과 같다. - 즉, d[i][j]=d[i-1][j-1]+d[i-1][j+1]이다. - j가 0일 때, 9일 때는 각각 1과 8밖에 연속하는 수가 없으므로 예외처리해준다. import java.util.Scanner; public class BOJ10844 { static final long mob..
N개의 카드를 1~N개짜리 카드팩으로 고를 때 가장 비싸게 사는 가격을 찾기 - 1~n개의 카드가 들어있는 카드팩의 가격을 p[1]~p[n] 배열에 저장한다. - 1~n개의 카드를 고를 때 가장 비싸게 가격을 d[1]~d[n] 배열에 저장한다. - if(d[x]>0)으로, 메모리제이션을 확인한다. 없으면 시간 초과발생. - x개를 고를 때, x-1개를 가장 비싸게 사고, 1개짜리 카드팩을 사는 경우, x-2개를 가장 비싸게 사고, 2개짜리 카드팩을 사는 경우, ... 0개를 가장 비싸게 사고, x개짜리 카드팩을 사는 경우까지 가격을 반복문으로 비교하며 최대가격을 d[x]에 저장한다. import java.util.Scanner; public class BOJ11052 { public static void..
