본문 바로가기

다이나믹 프로그래밍15

[2156] 포도주 시식 - C++ 몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고) 어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다. $DP [1] = wine [1]$ $DP [2] = wine [1] + wine [2]$ 로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문 이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자. 이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다. 1 번째 경우 이렇게 DP [i-2] 번째 잔까지.. 2023. 7. 2.
[2133] 타일 채우기 - C++ 2시간 정도 고민하며 여러 가지 아이디어들을 구현해 보도 결국에는 답을 보았다. 문제 1. N이 홀수 라면 타일을 채울 수 없다는 것을 알아냈다. 꾸역꾸역 채워 넣어도 한 칸이 남는 것을 알 수 있다. 2. $3\times 2$ 타일의 경우의 수 밑에 그림처럼 3가지 가능하다 N이 4일 때부터 DP를 채워 주면 될 듯싶다. 3. $3 \times 4$일 때 $$ 3 \times 3 = 9$$ 또 특수케이스를 고려해 줘야 하는데 아래처럼 2가지가 있다 직접 그려보면 알겠지만, 각 숫자에 존재하는 특수케이스는 두 개뿐이며 위 두 개 이외는 모두 중복이 됨을 알 수 있다 총 $9 + 2 = 11$가지 4. $3 \times 6$일 때 $$11 \times 3 = 33$$ 여기서부터 중복이 발생하게 되는데, 어.. 2023. 6. 29.
[10942] 팰린드롬? - C++ 문제 모든 경우의 수를 확인하는 브루트 포스로 푸는 것은 불가능해 보인다. N은 최대 2000개 이고, 질문의 개수가 최대 1,000,000개 [ 1, 2000 ]이라는 질문이 1,000,000개 나온다면 20억 번 연산을 해야 하므로 0.5초 안에는 절대 불가능 Q. DP로는 가능 할까? A. 가능하다. 점화식 명령 : [ 1, 7 ]이 팰린드롬이지 확인하고 싶다면 [ 2, 6 ] 이 팰린드롬 인지 확인 하고 [ 1 ] == [ 7 ]이 같은 지 확인해 주면 된다. 그런데 또 [ 2, 6 ]이 팰린드롬인지 알려면 [ 3, 5 ]를 알아야 하므로 DP로 풀 수 있다. 테이블 정의 DP [ i ][ j ] = i번째부터 j번째 까지가 팰린드롬 인지 확인 Boolean Type 입력받기 for(int i =.. 2023. 6. 27.
[11057] 오르막 수 - C++ 문제 왜 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번째 숫자가 처음인 상태에서의 최대 경우의 수 위의 설명은 좀 어려울 수 있으니 그림으로 보자 그림.. 2023. 6. 26.
[9465] 스티커 - C++ 이 글은 정말 이해가 가지 않는 분들을 위해 쓰인 글입니다. 문제 브루트 포스를 생각할 수 도 있지만 $ 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.. 2023. 6. 26.
[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.

티스토리툴바