DP

1. 개요 안녕하세요. 이 문제의 유형은 브루트포스입니다. 저는 다이나믹 프로그래밍을 사용해서 풀었습니다. 그러나 윗면과 아랫면이 여러 개 맞는 경우는 없고 모두 결정되어있기 때문에 브루트포스로 풀이해도 상관없을 것 같네요. 2. 문제 풀이 dp 테이블은 다음과 같이 구성했습니다.d[i][j]: i 번째 주사위의 j 번째 면이 윗면일 때 1...i까지 쌓은 주사위 탑의 옆 면의 최댓값 그 다음은 j 번째와 j의 반대편 면을 제외한 옆면의 최댓값을 찾아서 더해주시면 끝입니다. 3. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef ..

1. 개요 안녕하세요. "1103번 게임" 문제의 유형은 dfs를 응용한 다이나믹 프로그래밍입니다. dfs는 재귀로 구현하는 방법과 스택을 사용한 반복문 풀이가 존재합니다. 마찬가지로 다이나믹 프로그래밍도 재귀 + 메모이제이션을 사용한 top-down approach와 반복문을 사용한 bottom-up approach가 존재하죠. 둘 다 재귀로 구현이 가능하다는 공통점이 있기도 해서 그런지 이 둘을 합쳐 응용한 문제를 종종 마주치긴 합니다. 원래 저는 bottom-up 풀이 위주의 다이나믹 프로그래밍 풀이를 하다가 dfs와 응용되는 문제를 좀 더 쉽게 접근하기 위해서 top-down 풀이법을 연습했었습니다. 개인적으로 다이나믹 프로그래밍의 구현 난이도가 bottom-up에 비해 top-down이 더 쉽기..

1. 문제 풀이 union-find를 통해 친구 관계를 이어주었다. 여기서 루트 값에 사탕의 개수를 넣어주었고, 각 집합의 인원수는 다른 배열에 저장하여 union을 진행했다. 이를 이용하여 knapsack dp를 사용하여 특정 집합의 인원을 표기해 주었다. knapsack 문제를 정말 오랜만에 풀어서 많이 헤매게 되었다. 2. 코드#include using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pl;typedef tuple ti; typedef tuple tl; typedef vector vi; typedef vector vl;typedef vector vpi; ty..