-

자두나무 2240 https://www.acmicpc.net/problem/2240 [문제 풀이]dp[T][W] 2차배열 생성하고,dp[T][W]는 T초에 W번 이동했을 때 먹은 자두의 개수 라고 했을 때W % 2 == 0일때 dp[i][j] = jadu[i] == 1 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j];W % 2 == 1일때 dp[i][j] = jadu[i] == 2 ? Math.max(dp[i-1][j-1] + 1, dp[i-1][j]+1) : dp[i-1][j]; 연산을 마치고 dp[T][0] ~ dp[T][W] 중 최댓값 출력 123456789101112131415161718192021222324252627282930313233343..

1학년 5557https://www.acmicpc.net/problem/5557 [문제 풀이]눈여겨 볼 점은 계산을 하다보면 범위가 int형 범위를 넘어갈 수도 있다는 점.상근이가 아는 수는 다행히 0부터 20까지라는 점이다. 1. 숫자의 개수 N을 입력받고 2. 다음 줄에 나오는 N개의 숫자를 long형 ar[]배열에 집어넣는다. 3. 2차원배열 dp[N+1][21]를 생성한다. 어떻게 풀어나갈 생각이냐면.... dp[i][j]를 'i번째 수 까지 계산을 했을 때 j를 만들 수 있는 경우의 수'로 생각한다. 예를들어, dp[1][8] = 1 (8 = 8) dp[2][5] = 1 (8 - 3 = 5) dp[2][11] = 1 (8 + 3 = 11) 이다. 4. dp[i-1][]와 dp[i][]와의 관계를..

케빈 베이컨의 6단계 법칙 1389https://www.acmicpc.net/problem/1389 [풀이 방법]이 문제 역시 dfs, bfs, 플로이드 와샬 알고리즘 등 다양한 방법으로 풀 수 있다.난 플로이드 와샬 알고리즘으로 풀어봐야지... 가장 간단한 방법인 것 같다. 1. 첫째 줄에 N과 K를 입력받는다. N은 정점, K는 간선의 수라고 생각했다. 2. relation이라는 N+1 X N+1 행렬을 생성 후 이후에 나오는 간선 정보들을 저장했다. 여기서, 1이 3을 알때 3도 1을 안다고 볼 수 있으므로 relation[1][3] = 1 relation[3][1] = 1 을 해준다. 3. 탐색을 시작한다.relation[r][k] != 0이고 relation[k][c] != 0 일때 -relat..

경로 찾기 11403https://www.acmicpc.net/problem/11403 [문제 풀이] 이 문제를 푸는 방법은 여러 가지가 있다. 나는 bfs, dfs, 플로이드 와샬 알고리즘 중 플로이드 와샬 알고리즘을 이용해 풀었다.플로이드와샬 알고리즘은 형태가 정해져있기 때문에 모든 경로를 탐색하는 문제에 적용하기 쉬운 것 같다. 1. 모든 입력은 0과 1로 이루어져있다. 나는 입력을 받은 후 int형으로 바꾸지 않고 String형 그대로 map에 저장했다. 2. 정점 r에서 k로 가는 경로가 존재하고, 정점 k에서 c로 가는 경로도 존재한다면 정점 r에서 c로 가는 경로 또한 존재한다고 볼 수 있기 때문에 map[r][c]를 1로 설정해 주면 된다. 3. 탐색을 모두 마치고 출력하면 끝. 12345..

K번째 수 11004https://www.acmicpc.net/problem/11004 [풀이]숫자의 최대 입력 개수가 꽤 크다.수 정렬하기 3번 문제가 생각나서 비슷하게 풀려고 했으나 입력받은 수의 범위가 -10^9 < A < 10^9여서 포기.정렬 하면 분명히 시간초과걸릴텐데.... 하며 고민하던 중퀵소트를 변형해서 풀어보기로 했다. 설명하기가 좀 애매한 관계로 소스코드를 참고해 보자 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.InputStreamReader;i..

수 정렬하기 3 10989https://www.acmicpc.net/problem/10989 [풀이 방법]무턱대고 정렬 알고리즘으로 정렬을 시도했다간 시간초과 나기 십상이다. 퀵소트로 해도.그도 그럴것이 정렬해야 하는 숫자의 개수가 최대 10000000개 니까 정렬 말고 다른방법으로 풀어야한다. 여기서 힌트를 얻은 곳은 입력되는 수가 최대 10000이라는 것!크기 100001 짜리 배열 ar을 생성한 후 입력받은 숫자의 인덱스의 값 ar[index]를 1 증가시켜준다. 입력을 다 받았으면 ar[1]부터 ar[10000]까지 해당하는 값 만큼 index를 출력해준다. 1234567891011121314151617181920212223import java.io.*; class Main { public sta..

더하기 사이클 1110https://www.acmicpc.net/problem/1110 [풀이] 문제에 풀이과정이 다 나와있기 때문에 차근차근 문제의 설명을 따라가면 어렵지 않게 풀 수 있다.10의자리와 1의자리를 구하고 left = num / 10 (10의자리) right = num % 10 (1의자리)다음 숫자를 구한 다음 count++해준다. tmp = right*10 * (left+right)%10새로운 숫자의 10의자리와 1의자리를 구한다. ll = tmp/10 rr = tmp%10left 와 ll 그리고 right와 rr이 같은지 체크한 뒤같으면 count 출력같지 않으면 위의 작업 반복해준다. 123456789101112131415161718192021222324252627import jav..

숫자삼각형 1932https://www.acmicpc.net/problem/1932 [문제풀이]작성중 123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int row = Integer.par..

계단오르기 2579https://www.acmicpc.net/problem/2579 [문제 풀이] i번째 계단을 밟았을 때 최댓값은 두 경우 - i-2번째 계단 밟고 i번째 밟을 경우 - i-1번째 계단 밟고 i번째 밟을 경우중 최댓값을 고르면 답!!??이 아니라 틀린다!! 2번조건 "연속된 세 개의 계단을 밟으면 안된다"는 조건이 있기 때문이다! 자, 그러면 어떻게 풀어야 할까?일단 2차원 배열을 생성한다. i번째 계단을 밟았을 때 1) 1번 연속으로 밟은 경우 : dp[1][i] 2) 2번 연속으로 밟은 경우 : dp[2][i]두 경우로 나눌 수 있다! 이때, 1) i번째 계단을 1번 연속으로 밟기 위해서는 i-2번째 계단에서 2칸 이동하는 방법밖에 없으므로 dp[1][i] = max(dp[1][i-..

이친수 2193https://www.acmicpc.net/problem/2193 [문제 풀이]자리수 : n dp[i][0] : i자리 이친수 중 0으로 끝나는 이친수의 개수dp[i][1] : i자리 이친수 중 1로 끝나는 이친수의 개수 dp[i][0] = dp[i-1][0]+dp[i-1][1]dp[i][1] = dp[i-1][0] 답 : dp[n][0]+dp[n][1] 1234567891011121314151617181920212223import java.io.BufferedReader;import java.io.InputStreamReader; /* * 2193번 이친수 */public class Main{ static long d[][]; static int n; public static void m..