study

문제 문제해결 1. 주어진 배열을 뒤집으면 최장 증가 부분 수열 문제 푸는 방식으로 풀수있다 2. 숫자가 하나일때 최장 길이는 1이므로 dp 배열을 1로 초기화 한다 3. 반복문을 돌며 arr[j]

문제 문제해결 1. 금의 위치를 arr 배열에 담는다 2. 각 위치의 최고값을 기록할 dp 배열을 만든다, 맨 좌측은 더할 값이 없으므로 arr과 똑같이 초기화 한다 3. 점화식: dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]) - 이때 행이 아닌 열 순서대로 계산해야 하기 때문에 상위 반복문을 m만큼, 하위 반복문을 n만큼 돈다 - 맨 위 행일때랑 맨 아래 행일때는 i-1, i+1이 성립 안되기 때문에 if문으로 검사해준다 4. 맨 우측에 있는 열 중 가장 큰 값이 정답 import java.util.Scanner; public class Ex05_금광 { public static void main(String[] args) { S..

문제 해설 문제해결 1. 각 화폐 단위를 배열로 받는다 (int[] money) 2. 0~m원까지 가지고 있는 화폐로 만들 수 있는 최소 개수를 구하기 위한 dp 배열을 만든다 3. dp 배열의 0원은 0원으로 만들수있으므로(?) 0으로, 나머지는 10001(나올수 없는 최대값)로 초기화 한다 4. 2중 반복문을 돌며 각 화폐마다(mon) i-mon을 만들 수 있으면(dp[i-mon]!=10001) dp[i]와 dp[i-mon]+1의 최소값을 dp[i]에 넣는다 5. 마지막 dp[m]이 10001일 경우 구할 수 없는 경우므로 -1을 그 외는 dp[m]을 출력하면 된다 import java.util.Scanner; public class Ex04_효율적인화폐구성 { public static void ma..

문제 문제해결 - f(x)는 x를 1로 만들기 위한 최소 연산 횟수 - f(x) = min(f(x-1), f(x/2), f(x/3), f(x/5)) + 1 - 1을 빼는 연산을 제외한 나누기 연산들은 나누어 떨어질때만 포함될수 있음 - dp를 2부터 반복문을 돌면서 i번째 값에 f(i)를 집어넣음 - 나누기 연산은 나누어 떨어질 때만 연산 가능 import java.util.Scanner; public class Ex03_1로만들기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); //f(x)는 x를 1로 만들기 위한 최소 연산 횟수 //f(x) = min(f(x-1), f..

문제 문제해결 f(i)는 i번째 식량창고까지 얻을수있는 식량의 최대값이고 k(i)는 i번째 식량창고에 있는 식량의 양일때 f(i) = max(f(i-1), f(i-2) + k(i)) f(i-1) : i번째 식량창고를 약탈하지 않을때 f(i-2) + k(i) : i번째 식량창고를 약탈할때 둘중 더 큰 값을 dp 배열에 저장 import java.util.Scanner; public class Ex02개미전사 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.n..

피보나치 수열: a(n) = a(n-1) + a(n-2) 1) 탑다운 방식 import java.util.Scanner; public class Ex01피보나치수열_top_down { //100까지 담을 수 있는 배열 static long[] arr = new long[101]; public static long fibo(int x){ //종료 조건 명시 if (x==1 || x==2) return 1; //계산 했던건 그대로 출력 if (arr[x]!=0) return arr[x]; //처음 계산하는건 계산 후 배열에 담앋두기 arr[x] = fibo(x-1) + fibo(x-2); return arr[x]; } public static void main(String[] args) { Scanner s..

문제 - 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 위에 모든 숫자를 더한 값을 이어서 출력합니다. 입력 -> 출력 K1KA5CB7 -> ABCKK13 AJKDLSI412K4JSJ9D -> ADDIJJJKKLSS20 문제해결 1) 내 풀이 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String input = sc.nextLine(); int size = input.length(); char[] arr = new char[size];//알파벳만 꺼내서 담기 int num = 0;//숫자만 꺼내서 담기 for(int i..

문제 - 행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서 있습니다. - 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다. - 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있습니다. 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 - 이처럼 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하세요. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며 열 위치를 표현할때는 a부터 h로 표현합니다. 입력 -> 출력 c2 -> 6..

문제 - 정수 n이 입력되면 00시 00분 00초부터 n시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안되는 시각입니다. 00시 02분 55초 01시 27분 45초 입력조건 - 첫째 줄에 정수 n이 입력됩니다 (0

문제 - 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는(1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당합니다. 여행가 A는 상하좌우로 이동할 수 있으며, 시작 좌표는 항상 (1,1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다. L - 왼쪽으로 한칸 이동 R - 오른쪽으로 한칸 이동 U - 위로 한 칸 이동 D - 아래로 한칸 이동- 이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다. 예를 들어 (1,1)의 위치에서 L혹은 U를 만나면 무시됩니다. 입력조건:- 첫째 줄에 공간에 크기를 나타내는 N이 주어집니다.(1