문제 왜 DP를 써야 하는지 감조차 오지 않을 당신을 난 이미 알고 있다. 기본 적으로 입력이 1일 때는 10개이다. 0 1 2 3 4 5 6 7 8 9 2일 때 00 01... 09 - 10개 11 12... 19 - 9개 22 23... 29 - 8개 33 34... 39 - 7개 ... 99 - 1개 3일 때 000 001... 009 - 10개 011 012... 019 - 9개 022 023... 029 - 8개 ... 999 뭔가가 보인다면 대단한 것이며, 안 보여도 좋다, 당신의 눈을 뜨이게 하는 것이 나의 역할이다. Q. DP 테이블에 어떻게 의미를 부여해 줘야 할까? A. DP [i] = i번째 숫자가 처음인 상태에서의 최대 경우의 수 위의 설명은 좀 어려울 수 있으니 그림으로 보자 그림..

이 글은 정말 이해가 가지 않는 분들을 위해 쓰인 글입니다. 문제 브루트 포스를 생각할 수 도 있지만 $ O(2^n) $이며 입력의 최대 값이 100'000만 인 것을 보아 불가능하다. Q. 과연 DP로는 풀 수 있을까? A. DP [i] = i번째 까지 스티커를 떼었을 때의 최댓값으로 놓고 푼다면 가능하다. 경우의 수들이 존재하는데 그림으로 보자 i번째 스티커를 떼기 위한 경우의 수들 떼려는 스티커 = 파란색 파란색을 뗴기 위한 전까지의 최댓값 = 주황색 위 그림처럼 4가지 존재하며 이것을 구현해 주면 된다. 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } in..

정말 너무 진이 빠진다ㅏㅏ 풀이 정사각형인지 판단하려면 어떻게 해야 할까? 위, 옆, 대각선을 확인하면 된다. 이걸로 이 문제는 해결이라 볼 수 있다. 점화식 $$\large dp [x][y] = min(\{dp [x-1][y], dp [x][y-1], dp [x-1][y-1]\})$$ 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, m; int arr[1002][1002], dp[1002][1002]; int main(){ init(); cin >> n >> m; //입력 for(int i = 1; i > str; for(int j = 1; j

풀이 먼저 내가 썼던 글을 보고 오도록 하자, 그래야 이 문제도 이해할 수 있다! https://juuuuung.tistory.com/126 [9251]LCS - C++ 풀이 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 [ juuuuung.tistory.com ※위의 글을 읽었다는 가정하에 풀이를 시작하겠다.※ 최대 공통 문자열의 수를 구하는 알고리즘(LCS) cin >> A >> B; for(int i = 1; i A >> B; ..

풀이 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개의..