Algorithm

처음에는 i, j를 i번째 숫자를 사용하고 j번째 숫자를 사용할 때의 2번째 유저의 점수를 나타낸다고 하고 풀었다. 그러나 이렇게 풀 경우 마지막 테케를 통과하지 못한다. 그래서 이렇게 푸는 경우 전부 맞다고 나온다. 하지만 뭔가 이상하다. 그래서 결국 해설을 보았는데, 비스하게 하지만 카드대결 / 버리기 의 경우로 나눠서 각각에 대회 최댓값을 구해야 한다 2. 카드를 다 쓴 놈들(i==n or j==n) 들에 대해서 최댓값을 계산한다. 따라서 0 1 은 A는 카드 하나도 안버리고 B가 카드 하나 버린 상태인 i, j 에서 다음으로 넘어간다고 생각해야 한다. Solution 챗지피티 말로는 카드가 남은 장수를 i, j로 두고 풀 수 있다고 한다 다만 마지막 dp[0][0]이 이해가 안되어서 위에 코드로 이해하였다. code

이 문제 같은 경우는 그냥 직관적으로 풀어도 통과하기도 한다 (실행 때 마다의 미세한 시간 차이 때문에) Naive Sol 하지만 우리는 최대부터 고려하면 되기 때문에, 그때의 최대만을 계속 뽑아낼 수 있는 heap을 쓸 수 있다 Sol

O(n^2m)이라서 틀리는 코

문제에서 루트노트 1개인지 루트를 제외한 노드들이 parent가 항상 1개인지 전부 연결되어있는지 를 체크해야한다 참고로 유방향 그래프임을 기억해야 한다. 1번은 간선 정보를 저장하며 1) 그 번호가 사용되는지, 몇개의 parent가 있는지 기록해둔다 이를 통해 root를 찾을 수 있고 1개인지 체크 가능하다 2번은 간선 정보를 통해 확인 가능하다 3번은 dfs를 돌려서 전부 visited되는지로 확인 가능하다 solution

쉬운 문제라고 하나, 기억할 부분이 있어서 간단하게 정리 solution dp를 경우의 수를 저장 하는것 여기서 순서를 고려하기 떄문에,. i-1, i-2, i-5 번째의 경우를 더해주기만 하면 됨 또한, 그렇게 때문에 dp[0] = 1 로 정해야함. (0을 만드는 방법의 수가 1가지라고 생각)

DP 연습을 하는 도중에 만난 문제이다. 문제를 이해하고 나면 되게 쉽게 풀 수 있는 문제지만, 나 같은 경우에는 스스로 의문속에 갇혀 해결에 어려움을 겪은 케이스였다 처음 생각한 잘못된 생각들 시작점에 대해 정렬 추가정보 그냥 시간의 흐름 (결론적으로) 흐름에 맞게 정렬되면 문제가 없기 떄문에, 시작점 기준으로 정렬해도 무관. dp를 기록할 때, 기존에 어떤 선분들은 선택했는지에 대한 정보를 같이 가지고 있어야 한다. 하지만 2번이 불필요하다는 것을 알게 되면 1번이 잘못된 것임을 알 수 있다. 2번이 불필요 한 이유: dp를 선분 i를 표함하는 최대 선택 가능한 선분 개수를 저장 끝점 기준으로 정렬하면 i 이전 선분들 중에서 i와 겹치지 않는 선분만 고려할 수 있음. 또한, dp에는 최적해만을 저장하게 되기 때문에, 다시 말해 최적 부분 구조와 중복된 하위 문제의 효율적 계산이라는 dp의 특성때문에, 항상 겹치지 않는 선분들을 선택하게 되고, 그중 최선의 결과를 저장하게 되므로 기존의 선택들을 고려할 필요가 없음 만약 idx가 필요하면 추적 필요 Solution

최근에는 3차원 BFS가 나오는 등 난이도가 더 괴랄해지고 있다. (그래서 탈락)