C++13 [2156] 포도주 시식 - C++ 몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고) 어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다. $DP [1] = wine [1]$ $DP [2] = wine [1] + wine [2]$ 로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문 이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자. 이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다. 1 번째 경우 이렇게 DP [i-2] 번째 잔까지.. 2023. 7. 2. [1915] 가장 큰 정사각형 - C++ 정말 너무 진이 빠진다ㅏㅏ 풀이 정사각형인지 판단하려면 어떻게 해야 할까? 위, 옆, 대각선을 확인하면 된다. 이걸로 이 문제는 해결이라 볼 수 있다. 점화식 $$\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 2023. 6. 23. [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. [2294] 동전 2 - C++ 안 좋은 풀이와 좋은 풀이 두 가지 다 보여 드리겠습니다. 안 좋은 풀이 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 2023. 6. 22. [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. 이전 1 2 3 다음
