탕구리's 블로그

그냥, 규칙을 찾으면 되는 문제! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by idongsu on 2017. 7. 30.. */ public class num_9461 { static public void main(String args[]) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(in.readLine()); long dp[] = new long[101]; dp[1] = 1; dp[2..

동적계획법(Dynamic Programming) 말 그대로 파일을 합치기 위해 가장 최소가되는 비용을 찾는 문제이다 예시 처럼 40,30,30,50 일경우 방법 1. 40,{30,30,50} 방법 2. 40,{{30,30},50} 방법 3. 40.{30,{30,50}} 방법 4. {40,30},{30,50} 방법 5. {40,30,30},{50} 방법 6. {{40,30},30},{50} 방법 7. {40,{30,30}},{50} 이런 식으로 문제를 해결하되 이중 최소의 값을 출력 값으로 선택한다. (소스와 위의 방법의 예제와는 순서가 다를 수 있습니당) 사실, 인터넷을 통해 참고 했지만 소스를 이해하는데도 내것으로 만드는데도 많은 시간과 어려움이 있었다. 아직 너무 실력이 없기 때문에 다른 분들도 슬퍼..

동적계획법(Dynamic Programming) Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] d = new int[1001]; d[0] = 1; d[1] = 1; for (int i=2; i

동적계획법(Dynamic Programming) 타일을 구성할 수 있는 방법에 대해 재귀를 이용하여 Dp배열을 완성 항상 기준은 1,2, ... N 일때 i 번째를 기준으로 앞 쪽에 저장된 Dp값을 이용하면 된다. static public void main(String args[]) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(in.readLine()); long[] dp = new long[N+1]; System.out.println(solve(N,dp)%10007); } static long solve( int N, long[] dp..

동적계획법(Dynamic Programming) LIS라는 기법(?) 방식을 통해 Dp를 이용하여 해결! BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(in.readLine()); int[] arr = new int[N+1]; int[] dp = new int[N+1]; int max =0; st = new StringTokenizer(in.readLine()); int last=0; for(int i=1; i dp[i]) { dp[i] = dp[j] + 1; } } max = Math.max(max,dp[i]); } System.out.p..

동적계획법(Dynamic Programming) DP를 이용하여 모든 경로를 탐색하되 지난적 있는 경로에 대해서는 Dp배열의 값을 이용하는 방법으로 해결 재귀를 이용하여 문제를 해결하였다. BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; String[]k = in.readLine().split(" "); int row = Integer.parseInt(k[0]); int col = Integer.parseInt(k[1]); int[][] arr = new int[row+1][col+1]; int[][] dp = new int[row+1][col+1]; int result = 0; for..

동적 계획법(Dynamic Programming) 기초 문제는 저번에 풀었던 RGB 풀이와 약간 비슷했다N번째가 생길 수 있는 경우를 생각하면 되는 문제였다.

동적 계획법(Dynamic Programming) 기초 * 이웃하는 집과 같은색을 칠하면 안되는 것이 요점 * 첫번째 집이 빨간색일 경우 두번째 집은 초록 or 파랑 색만 색칠 가능하다. 처음에 생각한 풀이 방법은1번 집의 최소 비용을 결정하고 2번 집의 색과 비용을 결정할 때어떤 색을 1번에서 선택했는지 넘겨 주려 했지만.. 그 걸 처리하는 과정이 쉽지가 않았다. 인터넷을 통해 힌트얻어현재의 인덱스(n번째 집)을 기준으로 각 R , G , B 색을 결정 했을때n-1 번 집의 비용을 설정하는 방법을 사용하기로 하였다. 자꾸 짤려서 이미지로 대체 할게요..

동적계획법(Dynamic Programming) 기초 이 문제도 Top-Down 방식을 통해 해결 하였는데... 내가 생각한 Top-Down이 이게 맞는지 모르겠다.입력 받은 N을 기준으로각각, 3으로 나누기, 2로 나누기, 1을 빼기세 가지 방법을 시작으로 연산을 시작한다. 하나만 하는 것이 아니고 (3가지 방법을 모두 진행해 보고 그 중 최소값을 배열에 담아 두는 방식) 예를 들면 3을 1로 만드는 연산 방법은 3 / 3 = 1 의 방법과(3 -1) / 2 의 방법이 있기 때문에 그 중 연산횟수가 최소가 되는 첫 번째 방법의 연산 횟수가 구하고자 하는 출력 값이 된다. import java.io.BufferedReader; import java.io.IOException; import java.io...