동적계획법 15

BOJ#9084 동전

BOJ#9084 동전 * 문제https://www.acmicpc.net/problem/9084 * 풀이참고한 블로그 : http://wootool.tistory.com/177http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220793012348http://heygyun.tistory.com/46 동적계획법의 개념(복잡한 문제를 여러 하위 문제로 나누어 푼다)을 잘 생각해봅시다.dp[i] : 주어진 동전을 가지고 금액 i를 만드는 경우의 수 예를 들어 목표 금액이 30원이고, 동전이 5원, 10원짜리가 있을 때 일단은 5원짜리만 있다고 가정했을 때 dp[30] : 5원짜리로 30원을 만드는 경우의 수이제 10원짜리 동전을 추가해보자. dp[30] : 3..

Algorithm/DP 2017.05.01

BOJ#14501 퇴사

BOJ#14501 퇴사 * 문제https://www.acmicpc.net/problem/14501 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다. dp 문제입니다. 각 경우(상담)에 대해 상담하는 경우, 상담하지 않는 경우 2가지 경우로 나눌 수 있습니다. 정의 및 점화식dp[idx] : 날짜가 idx 일 때, 이후 얻을 수 있는 금액의 최대값dp[idx] = max(dp[idx+1], dp[idx + T[idx]] + P[idx]) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2314501_Retire/src/Main.java import java.io.BufferedReader; import java.io.IOException..

Algorithm/DP 2017.04.22

BOJ#1932 숫자삼각형

BOJ#1932 숫자삼각형 * 문제https://www.acmicpc.net/problem/1932 * 풀이 ▷ dp 정의dp[i][j] : i층에서 j 를 선택했을 때, 0~i 층의 최대값 ▷ dp 점화식dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1]) 별로 어렵지 않은 문제였지만 시간초과로 고생을 좀 했습니다. 원인으로는 dp 초기값을 0으로 설정했는데 코드 64라인에서 dp값을 재활용 할 때, 원래 삼각형 값이 0인 경우와 dp 초기값 0인 경우를 구분하지 못해서 메모이제이션을 하지 못했기 때문입니다. dp 초기값을 -1으로 고쳐서 해결하였습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/..

Algorithm/DP 2017.02.09

BOJ#1149 RGB거리

BOJ#1149 RGB거리* 문제https://www.acmicpc.net/problem/1149 * 풀이 ▷ 규칙 - 각 집은 R, G, B 3가지 색 중 한가지 색으로 칠한다. - 이웃한 집은 같은 색으로 칠하지 않는다. - 마지막 집은 R, G, B 3가지 색 중 하나이다. - 위 3가지 경우 중 최소값이 우리가 원하는 정답이다. ▷ dp 정의dp[i][RED] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 RED일 때 costdp[i][GREEN] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 GREEN일 때 costdp[i][BLUE] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 BLUE일 때 cost ▷ 점화식dp[i][RED] = min(dp[i-1][GREEN], dp[i..

Algorithm/DP 2017.02.08

BOJ#9251 LCS

BOJ#9251 LCS* 문제https://www.acmicpc.net/problem/9251 LCS(Longest Common Subsequence, 최장 공통 부분 수열) * 풀이 2개의 문자열의 공통 부분 문자열의 길이를 구하는 문제입니다.ex) abcd, bd 일 때 -> 공통 부분 문자열은 bd이고 길이는 2 dp 정의는 아래와 같고 dp[i][j] : s_1, ... , s_i와 t_1, ... , t_j에 대한 LCS의 길이 s_1, ... , s_i+1와 t_1, ... , t_j+1에 대해서 1) s_i+1 = t_j+1 이라면dp[i+1][j+1] = dp[i][j] + 1 2) s_i+1 != t_j+1 이라면dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])..

Algorithm/DP 2017.02.06

BOJ#2293 동전1

BOJ#2293 동전1 * 문제https://www.acmicpc.net/problem/2293 * 풀이정말 이해하기 쉽지 않은 문제였습니다.조금 더 완벽하게 이해한 후에 저의 풀이를 포스팅하도록 하겠습니다. 참고한 풀이 : http://blog.naver.com/occidere/220784778900import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2293 동전1 * https://www.acmicpc.net/problem/2293 */ public class Main { // dp[i] : n가지 종류의 동전..

Algorithm/DP 2017.01.24

BOJ#2011 암호코드

BOJ#2011 암호코드 * 문제https://www.acmicpc.net/problem/2011 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 숫자의 범위가 1~26이므로어떤 해석할 수 있는 암호가 주어졌을 때, 마지막 숫자는 아래와 같이 3가지 경우로 나눌 수 있습니다. 그리고 아예 해석할 수 없는 경우도 있습니다. (dp[i] : i번째 숫자까지 해석했을 때, 해석의 가짓수)1) 한 자리수로만 해석할 수 있는 경우예 : "251" → 마지막 숫자 "1"은 "1"로 해석 가능하나, "51"로는 해석할 수 없다. 즉, "25"에서 "1"을 추가한 경우 dp[i] = dp[i-1]; 2) 두 자리수로만 해석할 수 있는 경우 예 : "2510" → 마지막 숫자 "0"은 "10"로 해..

Algorithm/DP 2016.12.12

BOJ#2225 합분해

BOJ#2225 합분해 * 문제https://www.acmicpc.net/problem/2225 * 풀이dynamic Programming 문제입니다. 예를 들어 2 2가 입력된 경우 아래와 같이 3가지 경우가 있을 수 있습니다.0 + 21 + 12 + 0 3 2가 입력된 경우에는0 + 31 + 22 + 13 + 0 4 2가 입력된 경우에는0 + 41 + 32 + 23 + 14 + 0 감이 오시나요?어떻게 풀어야 할지 모를때는 예제의 숫자를 낮춰서 생각하면 좋습니다. " N K가 입력된 경우에서첫번째 숫자가 m으로 정해지면나머지는 N-m K-1의 경우가 됩니다. " dp를 아래와 같이 정의하고 위 내용을 구현하시면 되겠습니다. - dp[N][K] : 0~N까지의 정수 K개를 더해서 그 합이 N이 되는 경..

Algorithm/DP 2016.12.09

BOJ#1699 제곱수의 합

BOJ#1699 제곱수의 합 * 문제https://www.acmicpc.net/problem/1699 * 풀이Dynamic Programming 문제입니다. 주의할 점으로,Greedy 하게 풀면 안됩니다. 반례로 12의 경우를 생각해보시면 되겠습니다.ex) 12 = 3^2 + 1^2 + 1^2 + 1^2 (4) = 2^2 + 2^2 + 2^2 (3) 따라서 동적계획법을 이용하면서 완전 탐색을 해주시면 됩니다. - 비슷한 문제 https://www.acmicpc.net/problem/1463 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231699_SumOfSquares

Algorithm/DP 2016.12.08