이해 분리 집합으로 풀면 된다. i,j를 union하고 m개의 첫번째와 입력받는 m-1개가 연결되었는지 확인한다. 틀렸습니다 92%에서 계속 틀리길래 한참 고민했는데 디버깅 해보니 아니 나는 무슨... union 해주는 과정에서 Parent를 초기화해서...(왜? 아마 코드 줄이려고 그런 흐린 판단을 했던 것 같다...) 내가 한 실수 이외에도 계속 AC를 못 받는다면 index를 1부터 저장해보는 것도 방법일 수 있다. 질문 검색해보니 그런 케이스가 좀 있는 것 같았다. 코드 #include #include #include using namespace std; using ll = long long; const int MAX = 210; const int INF = 987654321; int n, m; ..

이해 입력 D의 범위 안에서 최대 점수('현재 점수 * 다음 점수'의 합)을 구한다. 입력받은 2차원 배열과 같은 크기의 dp[i][j]를 만들자. dp[i][j]가 i행 j열 까지의 최대 점수라고 할 때, dp[i][j]는 i행 j열로 가기 전 단계 x행 y열에서, 'x행 y열의 점수 * i행 j열의 점수' 연산을 더하는 값과, 더하지 않는 값 중의 최댓값이다. 따라서 dp[i][j] = max(dp[i][j], dp[x][y] + cur*next); 라는 점화식을 떠올리는 것은 쉽다. 틀렸습니다 70%쯔음에서 '틀렸습니다'를 받았다면 INF(dp배열 또는 답의 초기값의 최저)의 값을 너무 낮게 설정했을 수 있다. 메모리 초과가 났다면 입력의 2차원 배열을 int arr[100001][100001]로 ..