답은 알고리즘 뿐이야!

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN 풀이 : 완전탐색과 DP를 합쳐놓은 문제입니다. 우선 완전탐색으로 행렬을 찾고 연쇄행렬 최소곱셈 알고리즘을 사용하면 됩니다.(DP) 행렬을 찾는 과정은 제약 사항 중 부분 행렬의 열의 개수는 서로 다르며 행렬의 행의 개수도 서로 다르다는 조건에 따라 [SWEA 1259] 금속 막대 이 문제에서 설명 드린 것과 유사하게 찾을 수 있습니다. N X M 행렬에서 N부분은 check 배열에서 ++, M부분은 check 배열에서 -- 하여 유일한 곱셈 순서를 찾고 연쇄행렬 최소곱셈 알고리즘을 사용합니다. (55 ~ 66라인) ..

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN 풀이 : DP문제라고 해서 보긴 했는데 DP로 푸는방법이 떠오르진 않네요 ㅠㅠ 혹시 DP로 푸신분있으면 가르쳐 주시면 감사하겠습니다... 너무 야매로 푼거같아서 어떤 알고리즘으로 풀었다고 해야 할 지 모르겠네요... 일단 이 문제는 수나사와 암나사의 사이즈를 맞춰서 최대로 연결하는 문제입니다. 문제의 조건이 너무 불충분해서 제가 테스트 케이스로만 분석하여 수나사와 암나사의 최대 크기는 30, 금속 막대의 개수는 20개로 놓고 풀었습니다. 그다음 마찬가지로 조건이 너무 불충분 하여 두가지 가정을 하였습니다. 가정 1) ..