풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [i][j-1] 둘 중 큰 값을 구한다. 그림 설명 더보기 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } string A, B; int dp[1003][1003]; int main(){ init(); cin >> A >> B; for(..

안 좋은 풀이와 좋은 풀이 두 가지 다 보여 드리겠습니다. 안 좋은 풀이 DP테이블을 이차원 배열로 놓고 풀었다. 행 ( row ) = 내가 가진 동전의 순서 열 ( column ) = 만들 수 있는 임의의 가치 먼저 코드를 보고 그림으로 이해해 보도록 하자 //상수 #define MAX 2E+9 //변수들 int n, k; int coin[101]; int dp[101][10'002]; //입력 cin >> n >> k; for(int i =1; i > coin[i]; //실행 로직 for(int i = 1; i

브루트 포스로 문제를 풀어야겠다는 생각 조차 하지 못했다. 풀이 수빈이는 현재 100번 채널에 있다. 부서진 리모컨 입력 받기 부서진 리모컨의 번호를 bool 배열로 표시한다. bool breakDown[11]; //부서진 번호 입력 for(int i = 0; i > num; breakDown[num] = true; } 초기 최솟값 설정 최소 이동을 표현하기 위한 minimum 변수를 만드며, 초기값은 abs(n-100) int minimum = abs(n-100); 위처럼 구현한 이유는? 만약 n 이 100보다 작을 수 있기 때문에 예) n = 10, mnimum = 90, 현재로서 최솟값은 90번 ( - ) 버튼을 눌러야 10에 도달할 수 있다. 연산 로직..

이번 문제는 잘못된 풀이 또한 함께 제시해 보려고 한다. 잘못된 아이디어 이차원 배열로 풀 수 있을 것 같다 DP [101][10'001] 이차원 배열은 불가능한 듯하다 $$101 \times 10'001 \times 4 = 4'040'404byte = 4.040404mb$$ 최대 4mb인데 4mb를 넘어가 버린다 점화식 $$dp [j][i] = dp [j][i-coin [j]]\; + \;dp [j][i]\; + \;\sum_{k = 1}^{j-1} dp [j-k][i-coin [j]]$$ 답은 맞게 나온다 사실 맞는 지도 모른다..., 하지만 메모리 초과가 뜬다.... 그래도 열심히 풀었으니 코드는 올려본다 #include using namespace std; void init(){ ios_base:..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이게 실버 4라고? ㅎ... 풀이를 시작하기전 말할 것이 있다면 나는 좀 이상하게 푼 것 같다.... 뭐지 일단 시작 하겠다. 풀이 ( 주의! ) 처음에 문제 이해를 잘못한 나머지 항상 B 일 때만 계산했다. 왼쪽 위가 B로 시작할 때, W로 시작할 때 둘 다 계산해줘야 한다. 가장 먼저 우리가 해야 하는 8 x 8로 자를 수 있는 모오오든 경우의 수를 구해야 한다. 8 x 8로자를 수 있..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 정후이 폼 미쳐 따이.... 드디어... 드디어 내 혼자 힘으로 DP 문제를 풀어 버렸다... 이게 무슨 일인고 풀고 난 후에 다른 사람들 풀이를 봤을 때 좀 이상하게 푼 감이 있지만 일단 풀이를 시작하겠다! 아이디어 최근에 KnapSack문제가 인상 깊어서 그런가? 이 문제도 비슷하게 풀 수 있을 것 같았다. DP테이블을 이차원으로 정의 행(row) => i번째 카드 번호 열(column) => j개의..

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 정말 미세하게 DP에 대한 감이 잡히기 시작한 것 같다. DP문제라는 것을 알고 풀긴 했지만! 점화식을 찾아냈다는 것이 뿌듯했다. 하지만 점화식을 찾아낸 것 그뿐이고 그다음을 어떻게 해야 할지 몰라 답을 찾아서 봤다....ㅎ 풀이 먼저 점화식을 찾아낸 방법은 하나하나 다 써봤다. 이것만큼 좋은 게 있을까? $$\Large d[i] \space =\space d[i-1] \space + \space d[i-2]..

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 진짜 너 어어어ㅓㅇ무 어려웠다 답을 보면서도 이게 왜? 대체 왜? 라는 생각이 끊이질 않았다. 이러한 문제를 KnapSack Problem(배낭 채우기 문제)라고 말한다. 풀이 일단 다이나믹 프로그래밍을 사용해서 풀어야 된다. (진짜 정말 어떻게 이걸 다이내믹 프로그래밍으로 테이블을 정의해서 풀어낼 생각을 한 걸까? 미친 걸까? 대..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 일단 예전에 풀었던 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 사용하는 것이라는 건 자명한 사실! 하지만 여기선 추가 된것이 있었으니, 그 경로까지 구해야 하는 것이다. 이슈다 응용은 못한다.... 일단 당연히 문제에 대해 고민을 해보고 답을 봤다. 풀이 아이디어 가장 긴 배열을 구하며 경로도 추가 적으로 pr..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 진짜 정말..... 너무 어려웠다 답을 봐도 왜 이렇게 풀었는지를 몰라 계속 봤고 지금은 조금 이해한 상태다 DP 진짜 너무 어렵다.... 에효.... 아이디어 먼저 몇 가지 가능성을 보도록 하자 1. 현재 나의 위치에 자두가 떨어진다 a. 가만히 있고 자두를 잡는다 2. 현재 나와 다른 위치에 자두가 떨어진다 a. 다른 나무로 이동하여 자두를 잡는다 b. 가만히 있으며, 떨어지는 것을 지켜본다 코드로 구..