sncap Style

www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dfs 문제인 줄 알았는데.. DP 문제다. 잘 모르겠어서 이삭님 풀이 보고 풀었다. blog.naver.com/kdy246/222184773335 백준 알고리즘 - #2225 합분해 문제/생각 정리 문제문제 풀이한 방법이 문제는 다이나믹 프로그래밍을 활용하면 쉽게 풀 수 있었다.​생각해봐야 할 것은 ... blog.naver.com 파스칼의 삼각형 문제로 D[i-1][j] + D[i][j-1]을 반복해서 계산하는 형태이다. 그런데.. 왜 D[N][K] 가 답이 아닌 D[N][K-1] 이 답이 되는지는 모르겠다.. 움움 어렵네

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 어렵게 생각했는데.. 위상정렬 최대 값으로 해결함. DP import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public clas..

다이나믹 프로그래밍(Dynamic Programming) DP, 동적 계획법 Overlapping Subproblem 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 문제를 작은 문제로 쪼갤 수 있다 Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법 기본 전략은 문제를 작은 부분 문제로 나누는 것에서 부터 시작한다 작은 부분 문제를 해결한 결과로 큰 문제를 해결할 수 있다 특징은 중복되는 부분 문제들이 있다는 것 적용 방법 문제를 더 작은 부분 문제로 나눈다 중복되는 작은 부분 문제는 한 번만 계산해서 그 결과를 저장 중복되는 작은 부분 문제들은 여러 번 계산하..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 일반적인 배낭 문제로 1차원 DP로 풀이가 가능했다. D[무게] = {최대Value} 입력받은 V, W 값을 기준으로 각 무게별 Item을 추가했을때 최대 가치를 구하도록 했음. 코드 import java.io.BufferedReader; import java.io.FileInpu..

BOJ#2666 벽장문의 이동풀이법을 몰라서 서핑을 통해서 참조함[참조 : http://stack07142.tistory.com/157] * 문제https://www.acmicpc.net/problem/2666 * 풀이1. 문제 이해벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다. 열려있는 문이 이동하므로 2가지 경우가 발생합니다. 1) F가 이동하는 경우2) S가 이동하는 경우 2. 풀이 설계이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워..

문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 입력 :3 10 1 2 5 결과 10 D[N] = D[N-1] + D[N-2] + D[N-5] 풀이import java.io.BufferedReader; import java.io.FileInputStream; import java..

좌표 이동 경우의 수 구하기기본 nCr 문제이다. S A E N x M 의 경우 이며,이동시 경유지점 혹은 도착지점의 경우의 수를 구하면 된다.이동은 왼쪽 > , 아래 V 로 만 이동 가능하다.- 직항 : 출발 (S) > 도착(E)은 출발 점의 수 부터 nCr- 경유 : (출발(S) > 경유(A)) 의 수 x (경유(A) > 도착(E)) 의 수 nCr1 x nCr2[공식]일반 코드n C r = (n-1)C(r-1) + (n-1)C(r) DP code static int binomial(int n, int k) { if(BI[n][k]>0){ return BI[n][k]; } else if(k==0 || n==k){ return BI[n][k] = 1; } else return BI[n][k] = (bin..

https://www.acmicpc.net/problem/1149 DP를 이용한 문제. Home[i][j] = i번째집을 j색상으로 칠하려할때 i번째 집까지 도색할때 드는 최소 비용RGB[j] = 현재 집을 j색상으로 칠하려 할때 드는 비용 바로 이전 집의 모든 색상에 대해서 최소값을 비교하여 최소 값을 유지하는 방식 코드 import java.io.BufferedReader;import java.io.FileInputStream;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class boj1149 {static int N;static int[][] Home;static..