기록

구름 이라는 곳에서 문제 풀이 챌린지(구름톤 챌린지)를 한다고 해서 참여 중이다. 이벤트 기간 동안 문제가 꾸준이 올라오며, 주에 2회씩 (혹은 그 이상) 챌린지 문제들에 대해 풀이가 가능한 문제들을 풀이해보고, 후기를 남겨보려고 한다.

구름 이라는 곳에서 문제 풀이 챌린지(구름톤 챌린지)를 한다고 해서 참여하려고 한다. 이번주부터 1주차이며, 주에 2회씩 (혹은 그 이상) 챌린지 문제들에 대해 풀이가 가능한 문제들을 풀이해보고, 후기를 남겨보려고 한다.

풀이를 보면 매우 당연하지만, 그래프에 대한 개념이 확실히 되어 있지 않다면 아이디어 발상이 어려울 수 있다. 어떤 순서를 강제하는 것을 edge 연결로 볼 수 있고, 이런 조건을 만족하게끔 해둔 다음에 방문하지 않은 노드부터 차례대로 dfs로 방문해 나가면, 제일 끝에 도달하는 녀석이

LCS는 Longest Common Subsequence의 약자로 이 문제 제목에도 대놓고 쓰였다. 처음 접했을 때 생각하기 어려운 DP이고, 개같이 멸망. 아래 URL의 풀이를 거의 그대로 참고했다.

기존 RGB거리 문제의 강화판. 그래도 최근 DP 짬밥이 있어서 그런지 처음에 막혔어도 힌트 안보고 최종 풀이에 성공했다. 풀이 방식에는 여러가지가 있어 보이는데, 나는 DP 차원을 확장하는 것으로 해결했다.

Codeforces Round 874 E번 관련 기록.

예전에 스택으로 풀 수 있다는 이야기만 듣고 덮어놨었던 문제. 다이아몬드 가공 문제에서 최대 면적을 빠르게 구해야할 필요가 있어서 다시 꺼내 풀어보았다.

뭔가 발상이 잘 안떠오른다 싶으면 DP인듯. 시험 끝나고 반응을 보니 코포 DP 대표유형(?) 취급이다. 익숙해질 필요가 있는듯. 10^9 + 7 따위와 같은 수로 나누는 것도 DP 신호 중 하나. DP는 꾸준한 연습만이 살 길.

간단한 DP 연습 문제. 아래 점화식을 N = 3, 4, 5 반복해보면 관찰할 수 있다.

간단한 DP 연습 문제. 오르막 수는 n번째 자리에 올 수 있는 수가 n - 1번째 자리에 올 수 있는 수로 정해진다.