jwvg0425 Problem Solving

대회 링크 : http://codeforces.com/contest/1045 버블컵 미러에 koosaga님, breakun님과 팀으로 참가했다. 실력이 나랑 비슷하거나 그 이하인 사람과는 팀을 해 본 적이 있지만 나보다 압도적으로 잘하는 사람들이랑 팀을 해본 건 처음이었는데, 정말 너무 유익하고 재밌는 대회였다. 역시 팀으로 참가하는 대회가 개인전보다 훨씬 재밌다는 생각이 들었다. 대회는 무려 9문제를 풀어서 3등을 했고, 그 중에 내가 3솔브, koosaga님이 5솔브, breakun님이 1솔브를 하셨다. breakun님이 개인 사정으로 대회에 처음부터 참가하지 못하시고 중간부터 참가하게 됐는데 이게 너무 아쉽다. 처음부터 참가하셨으면 올솔브 가능했을 것 같은데 ㅠ 오늘 셋에서 내 실력에 풀 수 있을만..

한참 고민하다가 쿠사가님으로부터 힌트를 듣고 풀었다(원본 풀이는 큐브러버님 것이라고 함). 오늘 쉬운 것만 푼 것 같아서 이 문제를 잡았는데 정말 좋은 풀이여서 풀길 잘했다는 생각이 들었다. 문제 링크: https://www.acmicpc.net/problem/1848 문제 요약n개의 정점과 m개의 간선으로 이루어진 그래프가 있다. 각 간선은 a b c d로 표현되는데, 이는 a->b로 갈때는 비용이 c이고 b->a로 갈때는 비용이 a라는 뜻이다. 이 그래프에서, 1번 정점에서 시작해서 다시 1번 정점으로 돌아오는 최단 경로를 구해야 한다.이 때,1. 모든 정점과 간선은 딱 한 번만 지나갈 수 있다(1번 정점 제외)2. 1번 정점 외의 정점을 반드시 하나는 거쳐야 한다. 문제 풀이 1번 정점에서 임의의 ..

문제 링크: https://www.acmicpc.net/problem/8098 문제 요약n개의 구간이 있다. 각 구간은 (p,k)로 구성되며 각 숫자는 1이상 30000이하이다. 서로 다른 두 구간은 겹치게 선택할 수 없을 때, 선택한 구간들의 전체 길이 합의 최댓값을 구하여라(단, 두 구간에 대해 한 구간의 끝점과 다른 구간의 시작점이 같은 경우는 선택할 수 있다). 풀이일단 하나의 구간만 놓고 생각해보자. 특정한 한 구간을 골랐을 때, 이 구간을 맨 끝 구간으로 포함하는 길이 합의 최댓값은 어떻게 구할 수 있을까? 간단하게 생각하면, 현재 구간이 (l,r)일 때 1~l까지의 최댓값 + 현재 구간의 길이가 곧 전체 최댓값이 될 것이다. 이러한 논리를 반복적으로 적용하면, dp(pos) = 1 ~ pos..