ps

문제 링크8달 전에 dp를 통해 해결했었던 문제였지만, 오늘 재채점을 통해 틀렸습니다를 받아서 다시 풀게 되었다. 각 좌표를 정점으로, 1초후에 이동할 수 있는 점들을 연결하여 간선을 만들고 BFS를 통하여 n에서 k까지 갈 수 있는 최단경로를 찾음으로써 문제를 해결하

문제 링크약간 변형된 MST문제였습니다.각 도시는 어떤 발전소에서 전기를 공급받아도 상관이 없고, 한개에서만 공급받으면 됩니다.또한, 발전소 자체에서는 전기가 공급이 가능합니다.따라서 Union-Find자료구조를 이용하여 크루스칼 알고리즘을 통해 해결하였습니다.먼저 발

문제 링크 N 마리의 소가 있고, M개의 우유 먹는 순서가 주어졌을 때, 모순이 생기기 직전까지의 순서를 기준으로하여 가능한 순서중 가장 사전순으로 빠른 순서를 출력하는 문제였다. 문제의 정해는 모순이 생기는 지점 X를 이분탐색을 통해 찾고, 그 X까지의 간선정보를

문제 링크또다른 USACO문제다.눈이 쌓인 길이 있고, 각각의 신발에 대해서 최대 견딜 수 있는 눈 깊이와, 최대 보폭이 주어질 때, 각각의 신발에 대해서 이 눈길을 걸어갈 수 있는지 판별하는 문제였다.문제를 간단히 해보면 각 신발에 대해서 눈의 높이가 신발이 견딜 수

문제 링크N <= 100000이고 Q <= 100000일 때, 각 쿼리에서 k와 v가 주어지면 v에서부터 간선의 가중치가 k이상인 간선을 이용하여 몇개의 정점에 도달할 수 있는지 구하는 문제이다. Brute하게 풀면 쿼리마다 BFS를 이용해주면 되는데, 한번

문제 링크N <= 100000인 트리가 주어질 때, 간선이 1개인 정점을 exit로 정의하고, 농부들은 exit에서 출발한다고 할 때, k에서 출발하는 Bessie를 잡기 위해 최소 몇 명의 농부가 필요한지 구하는 문제이다.DP와 DFS를 이용하여 문제를 해결하였

문제 링크트리와 이미 칠해진 지점의 색깔이 주어질 때, 3가지 색을 이용하여 트리를 인접한 정점끼리는 다른 색을 가지도록 칠하는 경우의 수를 구하는 문제이다.이러한 문제는 트리 dp를 이용할 때 단골문제처럼 나왔던 문제였다.dpcur = cur에서 color을 칠했을

문제 링크각 음식마다 f와 s가 주어지고, 여러개 음식의 맛는 f들의 합, 매운정도는 s중 최댓값이라고 할 때, 연속된 음식을 선택해서 맛이 m을 넘는 경우 중 가장 매운정도가 적게 되는 경우를 선택하는 문제이다.이분탐색을 통해 해결하였다.길이가 n인 배열에서, 음식들

문제 링크solved.ac에는 플래티넘 5라고 나왔지만, 많이 어려운 문제였다.문제에서는 n 개의 배열을 m 개의 색깔을 이용해서 채우는 경우의 수를 물어보는데, 이때 색깔은 k의 길이를 가진 도장을 통해서만 채울 수 있다. 색깔을 덮어쓰는 것도 가능하다.dp를 통해

문제 링크n 개의 크기 m 짜리 정수 배열이 있을 때, 각 배열에서 하나씩 수를 골라서 n 개의 수들의 최댓값과 최솟값의 차이를 가장 작게 하는 것이 문제이다.priority_queue를 이용하여 해결하였다.brute 하게 풀면 모든 값에 대해 그 값이 최솟값일 때 n

문제 링크세그먼트 트리를 이용하여 해결하였다.다른 사람들의 코드를 보면 펜윅 트리를 이용해서 끝난 작업의 수를 카운트해주어서 해결하였는데, 나도 비슷하게 세그먼트 트리를 이용하였지만, 문제에 나와있는 그대로 lazy propagation이용해서 시뮬레이션하듯이 해결하였

문제 링크n과 m이 상당히 크므로 어떤 구간에 대해 팰린드롬인지 아닌지를 적어도 O(logn)안에 해결해야 하는데 도저히 모르겠어서 풀이를 찾아보니 처음보는 알고리즘이 있었다. O(n)만에 각 정점을 중심으로 하는 팰린드롬의 최대 길이를 찾을 수 있는 알고리즘이었다.M

문제 링크1) 내 친구의 친구는 친구다2) 내 원수의 원수는 친구다 이 두 가지를 이용해서 만들어질 수 있는 팀의 개수를 찾는 문제였다. 서로 친구이면 같은 팀에 들어가야 하고, 같은 팀에 속에 있는 사람들끼리도 모두 친구여야 하므로 disjoint set을 떠올릴 수

문제 링크트리 dp & 그리디를 이용하여 해결하였다.dpi = i의 간접 혹은 직접 부하에게 모두 전화를 돌리는데 걸리는 시간 으로 정의하고, 자식들의 dp값을 모두 저장한 다음, 내림차순으로 정렬한 후, 차례대로 1,2,...씩 더한 값중 최댓값을 그 노드의 dp값으

그래프 단절점, 단절선에 대한 개념을 여기서 접하게 되었고, 연습하는 겸 문제를 풀어보았다.11266 단절점문제 링크주어진 그래프를 DFS트리로 바꾸면서 단절점 여부를 판단할 건데, 어떠한 점이 단절점인지 확인하기 위해서는 그 점의 모든 자식들이 그 점을 이용하지 않고

문제 링크머지 소트 트리를 연습해보고자 풀어본 문제이다. 세그먼트 트리에서 값이 아닌 배열을 저장해서 관리하는 방식은 처음으로 해보았다. 이 문제에서 k번째의 값을 구하기 위해서는 이분 탐색을 이용하여서 주어진 구간에서 x보다 작은 수들이 k-1개 이하로 있으면 m을

문제 링크이 문제는 여기의 d번 문제와 비슷하다 라는 생각을 가지고 대단한 학생인 집합들을 union-find해주면서 해결할 수 있을꺼라는 생각을 하고 접근했지만, n이 7000이하인 D번 문제와는 달리 n이 50만 이하이기 때문에 그런 접근 자체가 불가능했다. 끝없는

문제 링크간단하게 생각해보면 그냥 모든 경우, n!에 대해서 다 계산해주면 될 것 같지만, 15!은 10^12가 넘어가기 때문에 불가능하다. 집합에서 몇개의 수를 뽑으면 그 수들을 어떻게 나열하던간에 총 길이 합은 같다는 사실을 이용해서 비트마스크 dp를 이용하여 해결

문제 링크최선의 전략을 그리디로 짜보려고 했는데 어려움이 있었다. 그래서 DP를 이용해서 문제를 해결하였다. dpi = 근우의 턴에서 i~j까지 카드가 남았을 때 근우가 가질 수 있는 최대 점수라고 정의한다. 근우와 명우의 턴을 같이 계산하면서 dp를 전개해 나갈껀데

문제 링크SCC를 이용하여 해결하였다. 같은 정점, 간선을 여러번 사용할 수 있고, 최대 뽑을수 있는 현금을 계산해야 하기 때문에 어떤 정점에 방문했을 때, 그 정점이 속한 scc를 모두 방문하고 와야 한다. 따라서 scc중 한 점을 방문하는 것은 scc에 있는 모든

문제 링크최대, 최소 세그먼트 트리를 이용해서 해결하였다.주어진 문제에서 해결해야 하는 쿼리는 두 가지이다.1.선반 A와 B의 책을 바꿈2.L~R까지 책들이 L~R의 책으로 구성되어 있는지 판단1의 쿼리는 쉽게 해결할 수 있는데, 중요한 것은 2이다. 이 쿼리는 L~R

문제 링크이분 탐색을 통해 해결하였다.시간이 늘어남에 따라 태울수 있는 사람이 증가함수의 꼴로 늘어나므로, 시간이 x일 때 n명 이상을 태울 수 있는가?를 결정함수로 하여 이분 탐색을 적용하는데 문제가 없다. 따라서 n명이상을 태울 수 있는 최소의 시간을 찾아 준 후,

문제 링크쾨닉의 정리를 이용한 문제이다. 먼저 테이프는 겹쳐도 되고, 구멍이 뚫려있지 않은 부분은 테이프를 붙일 수 없다는 문제의 조건에 따라서 붙여야 하는 테이프의 크기를 최대로 해서 테이프를 붙일 가로 테이프, 세로 테이프를 정리한다. 그렇다면 테이프는 최대 n\

문제 링크힘들게 해결했다.처음에 문제를 보고 사이클이 생겼을 때, 조금씩 빚을 상환해서 최소한의 돈으로 상환하는 것을 생각하고 풀었는데, 이 문제는 그런 게 아니라, 돈이 없으면 갚지 않고 있다가 돈을 시에서 지급해주던가, 다른 사람이 갚아서 돈이 생겨야지 일시불로 지

문제 링크접미사 배열을 이용하는 문제이다. 접미사 배열을 만든 후 lcp를 구하고, 그 중 최댓값을 구하면 문제에서 요구하는 두 번이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이 그 자체를 구할 수 있다. 접미사 배열을 구하는데에 O(nlogn^2), lcp를

문제 링크 두 수 a,b가 주어지고, 두 수 사이의 3의 배수이거나 숫자에 3,6,9중 하나라도 들어있는 수의 개수를 찾는 문제이다. 언듯 보면 굉장히 쉬운 문제인거 같지만, 이 문제의 특징은 무려 a와 b가 최대 10^100000이라는 것이다. 완전탐색의 ㅇ도 생각해

문제 링크소수를 이용해서 풀었다. min과 max의 범위가 최대 10^12이므로, 제곱이 되기 위한 수는 10^6까지만 봐줘도 된다. 10^6 까지 소수인 수들은 에라토스테네스의 체를 이용해서 구할 수 있다. 그 다음 이 문제의 특징은 min과 max의 차이가 최대

문제 링크휴가를 보내고 와서 한동안 뜸했는데 다시 시작해야겠다고 본 문제인데 결국 풀이를 봤다. 풀이를 볼 때마다 느끼지만 항상 내가 생각한 거에서 한 발짝만 더 갔으면 먼가 실마리가 잡힐 수 있었을 거 같은 느낌적인 느낌이 든다. 그게 능력인가. 아무튼 그렇다. 최근

문제 링크dp를 이용해서 해결하였다. 이 문제에서 가장 중요한 점은 힘과 지능이 정해지면, 깰 수 있는 퀘스트도 이미 정해져 있다는 것이다. 따라서 diffi를 힘 i, 지능 j에 도달했을 때, 최대로 찍을 수 있는 스탯의 개수로 정의하고, pointi를 힘 i, 지능