728x90 반응형 알고리즘 (C++)19 [백준] 다리 놓기 - DP 문제 보러 가기 해당 문제는 백준 DP 알고리즘 분류에서 Silver 5 문제입니다. 문제 설명은 생략하고 제가 생각한 풀이를 적어보겠습니다. 참고로, 저는 C++ 언어를 사용합니다. 같이 생각해보기? 왼쪽의 다리와 오른쪽 다리를 연결합니다. 또한 다리는 각 1대1로 대응되어 건설됩니다. 이때 다리 건설은 서로 겹치지 않는다고 했으니, 무조건 1대1 대응이 확정입니다. 그렇다면 다리의 수는 항상 오른쪽 구역이 더 많은데 서로 중복되는게 없어야 한다? 즉 순서는 상관 없지만, 중복되는 것을 빼고 계속 뽑는다는 의미겠죠? 예, 조합을 의미합니다. 오른쪽 기준 내가 왼쪽 구역에서 다리를 선택하겠어! 라는 생각으로 문제를 접근해봅시다. 시작 전에 조합 공식 기억나시나요? 여기 있습니다!! 출처는 인터넷 ㅎ 피보.. 2022. 11. 12. 이전 1 2 3 4 다음 728x90 반응형