골드 V4 [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 [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(.. 2023. 6. 23. [1107] 리모컨 - C++ 브루트 포스로 문제를 풀어야겠다는 생각 조차 하지 못했다. 풀이 수빈이는 현재 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에 도달할 수 있다. 연산 로직.. 2023. 6. 22. [2293] 동전 1 - C++ 이번 문제는 잘못된 풀이 또한 함께 제시해 보려고 한다. 잘못된 아이디어 이차원 배열로 풀 수 있을 것 같다 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:.. 2023. 6. 21. [2240]자두 나무 - c++ https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 진짜 정말..... 너무 어려웠다 답을 봐도 왜 이렇게 풀었는지를 몰라 계속 봤고 지금은 조금 이해한 상태다 DP 진짜 너무 어렵다.... 에효.... 아이디어 먼저 몇 가지 가능성을 보도록 하자 1. 현재 나의 위치에 자두가 떨어진다 a. 가만히 있고 자두를 잡는다 2. 현재 나와 다른 위치에 자두가 떨어진다 a. 다른 나무로 이동하여 자두를 잡는다 b. 가만히 있으며, 떨어지는 것을 지켜본다 코드로 구.. 2023. 6. 10. 이전 1 다음
