-

암호코드https://www.acmicpc.net/problem/2011 언뜻 보면 쉬운 dp문제처럼 보이는데.. 예외로 처리해줘야 할 사항들이 몇가지 있다.나는 그 사항들을 체크하지 않아 엄청 많이 틀렸다. 주어진 입력이 해석 가능한 숫자조합인지 꼭!!! 체크한 뒤 제거해 줘야 한다.체크해줘야할 사항들로는1. 0으로 시작하는 경우2. 0이 연속으로 나오는 경우3. 0 앞에 3~9의 숫자가 나오는 경우4. 그리고!! 출력은 10000000으로 나눈 나머지를 출력할것! 잊지말자. 이 모든 예외들을 처리해 준 후 dp[i] = dp[i-1] + dp[i-2](S.charAt(i) > '0' && (S.charAt(i-1) == '1' || ( S.charAt(i-1) == '2' && S.charAt(i) ..

욕심쟁이 판다 1937 https://www.acmicpc.net/problem/1937 map[][]에 대나무 숲 정보를 다 집어넣고 map[1][1]부터 dfs로 이동 가능한 곳 모두 탐색한 뒤 최댓값 출력하면 될것같은데...알고리즘 공부하던 초창기에 푼거라 빙빙 돌아간 것 같다.. 어쨋든, 코드를 설명하자면 1. bamboo[][] 배열에 입력받은 정보들을 집어넣는 동시에 ArrayList al에도 집어넣는다. 2. al을 대나무 양을 기준으로 sort 한다. 3. al에 들어있는 정보들을 하나씩 get 해와서 탐색한다. 4. 탐색 종료 후 최댓값을 찾아서 출력한다.이렇게 된다... 예전에 풀었던 문제를 다시 보니 뭔가 실력이 향상된것 같아 뿌듯하다. 물론 코딩테스트는 다 떨어졌지만..ㅠ__ㅠ 12..

연속합 1912https://www.acmicpc.net/problem/1912 [문제 풀이]dp[i]를 index가 i일때의 연속합이라고 정의하면 dp[i] = max(ar[i], dp[i-1]+ar[i])이런 점화식을 구할 수 있다. 우선 10개의 숫자가 입력됐을 때 방금 구한 점화식으로 연속합을 구해보면index 1 2 3 4 5 6 7 8 9 10 입력 10 -4 3 1 5 6 -35 12 21 -1 연속합10 6 9 10 15 21 -14 12 33 32 표와 같고, 연속합의 최댓값은 index가 9일때 33(12+21)이라는 것을 알 수 있다. 계산을 모두 마친 후, dp배열에 저장된 연속합들 중 가장 큰 값을 출력하면 끝!! 1234567891011121314151617181920212223..

자두나무 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][]와의 관계를..

숫자삼각형 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..

1로 만들기 1463https://www.acmicpc.net/problem/1463 [풀이방법]dp[i] = i를 1로 만드는 최소 연산 수 dp[i] = min(dp[i-1], dp[i/2], dp[i/3])+1 모든 연산을 마친 후 dp[i]를 출력하면 답! 123456789101112131415161718192021222324252627282930313233import java.util.Scanner;/* * X가 3으로 나누어 떨어지면, 3으로 나눔. * X가 2로 나누어 떨어지면, 2로 * 1을 뺀다. * 범위 : 1 2 -> 1이렇게 4번이 걸린다.

RGB거리 1149https://www.acmicpc.net/problem/1149 [풀이방법]dp[0][i] = i번째에 R을 칠할 때 까지 든 최소비용dp[1][i] = i번째에 G을 칠할 때 까지 든 최소비용dp[2][i] = i번째에 B을 칠할 때 까지 든 최소비용이라고 할 때 dp[0][i] = min(dp[1][i-1], dp[2][i-1])+i번째 R을 칠할때 드는 비용dp[1][i] = min(dp[0][i-1], dp[2][i-1])+i번째 G을 칠할때 드는 비용dp[2][i] = min(dp[1][i-1], dp[0][i-1])+i번째 B을 칠할때 드는 비용 dp[0][i], dp[1][i], dp[2][i] 중 최솟값을 출력하면 된다. 123456789101112131415161718..