DP문제 푸는 내내 점화식을 한번도 못찾았네요이번 문제 또한 다른 분들의 코드를 참고했습니다.경로를 찾는데 그 시점을 달리하여 문제를 키를 찾는 것은너무 어려운 것 같습니다. 풀이를 시작할 때도 N부터 차근차근 내려올 생각밖에 못했지1부터 올라와 최소값을 비교해서 찾는다는 방식은꿈에도 몰랐습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[N+1]; dp[0]=d..
알고리즘 풀이/백준
n번째 계단에 도달하는 방법은n-1번째 계단에서 1계단 올라가느냐n-2번째 계단에서 2계단 올라가느냐 2가지 방법이 있습니다.2가지 방법 중 큰 값을 넣어주시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] point = new int[T+1]; int count=0; int[] tp = new int[301]; for(int i=1; i
삼각형의 규칙을 찾아해당 좌표에 도달하는 가장 큰 값을 배열에 넣어주어마지막까지 도달하는데 필요한 가장 큰 거리를출력해줍니다. n번째 줄의 양사이드로 가는 경로는 단 1개이므로 그냥 넣어주면되고,양 끝의 사이에 있는 경로는 2가지가 되므로 그 둘 중 더 큰 값을넣어주면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] res = new int[T]; int ..
DP의 기본이 되는 문제입니다. 상식적으로 첫째 줄부터 최소값으로 시작한다고 한다고마지막 비용이 최소값이 아니라는 것만 숙지하여점화식을 정의하는 법을 배우고모든 줄의 각각의 RGB까지 도달할 때의 최소값을 구합니다. 문제에서 요구하는 마지막줄까지의 최소 비용은마지막줄의 R, G, B까지 도달할때 의 최소비용 3개중 가장 작은 값을출력시키면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Syst..
재귀함수로 하면 시간초과납니다.. 피보나치수열이 가진 규칙을 이용하여정확히 n번째 필요한 0의 개수를 활용하여1의 개수까지 함께 출력합니다.규칙을 찾는 것이 무엇보다 중요합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[] res_prt = new int[2]; for(int i=0; i
에라토스테네스의 체로 2부터 10000까지 범위의수를 소수판별하고그 배열을 이용하여 골드바흐파티션을 뽑아냅니다. 문제에서 주어지는 짝수의 소수 2개 조합은짝수를 2로 나눈 절반값을 기준으로 차이값이 동일하다는 것입니다. 전 이 규칙을 몰라서 구글링했습니다. 그 차이값을 0으로 시작하여 2개의 조합이 가장 차이가 적은소수가 될 때까지 while문을 돌린 후출력해냅니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = ne..
방금 전에 익힌 에라토스테네스의 체를 이용하여 문제를해결합니다. 주의해야할 점은 boolean배열을 하나만 이용하여문제를 해결해야한다는 점입니다. 저 같은 경우는 getprime메소드 안에boolean 배열을 넣어 소수를 구할 때마다배열을 선언해야 하는 바람에 한번 틀렸습니다.크기 또한 문제에서 요구하는 n
에라토스테네스의 체가 뭔지 알면 쉽습니다 먼저 공부부터 하고소수 구하기를 구현하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int start = sc.nextInt(); int end = sc.nextInt(); boolean[] res = new boolean[end+1]; for(int i=2; i
숫자 1개인 경우가 예외입니다. 1-100 결과값 -> -100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int result[]; public static void mergeSort(int left,int right,int[] arr) { // 숫자열을 가져와서 1개 단위로 쪼개는 ..
예외는 M이 1인 경우입니다. 1 1 -> 결과 : -1 1 3 -> 결과 : 52 sosu라는 변수를 통해 일단 sosu라고 가정한 후sosu가 아닌 조건 즉, 숫자가 1이라 count가 1인 경우와count가 2일 때, 해당 값까지 for문이 미치지 못한 경우를구분하여소수일 때만 sum값에 더해주면 됩니다.최소값을 편하게 구하기 위해 큰 값부터 소수판별을 시작해서 작은 값으로내려갑니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42import java.util.*; public class Main { public static void mai..
