알고리즘 공부방

문제 https://oj.uz/problem/view/JOI20_ho_t3 문제 보기 - Collecting Stamps 3 (JOI20_ho_t3) :: oj.uz 문제 보기 - Collecting Stamps 3 (JOI20_ho_t3) oj.uz 원 위에 수행해야 하는 작업들의 위치 X, 수행해야 하는 시간 T가 주어질 때 원점에서 출발하여 각 시계방향, 반시계방향으로 움직이며 작업들을 수행해야 한다. 좌표 1칸을 이동할 때 1의 시간이 소요되고, 작업을 T이내에 수행한다면 보상을 받을 수 있을 때 전체 보상의 최대값을 구해야 한다. $N

문제 https://oj.uz/problem/view/JOI20_ho_t2 문제 보기 - JJOOII 2 (JOI20_ho_t2) :: oj.uz 문제 보기 - JJOOII 2 (JOI20_ho_t2) oj.uz 길이 $N$의 문자열과 $K$가 주어졌을 때 J, O, I의 연속한 $K$개의 문자로 이루어진 JJJJJOOOOOIIIIII와 같은 문자열을 만들어야 한다. 할 수 있는 연산은 (1) 왼쪽, 오른쪽에서 문자 제거 / (2) 중간에 있는 문자 제거 의 2가지 연산일 때 2번 연산의 수를 최소화해야 한다. $N

문제 https://oj.uz/problem/view/JOI20_ho_t1 문제 보기 - Just Long Neckties (JOI20_ho_t1) :: oj.uz 문제 보기 - Just Long Neckties (JOI20_ho_t1) oj.uz 길이 $N+1$의 배열 A, 길이 $N$의 배열 B가 주어졌을 때 $1

문제 https://oj.uz/problem/view/JOI17_rope 문제 보기 - Rope (JOI17_rope) :: oj.uz 문제 보기 - Rope (JOI17_rope) oj.uz 각 칸이 색칠되어 있는 배열 하나가 주어진다. 이 배열을 "접는다"는 것은 왼쪽 끝으로부터 어느 구간을 잡고, 그 구간을 제거한 후 뒤집어서 남은 배열의 왼쪽에 겹치도록 붙이거나, 같은 작업을 오른쪽 끝에서 하는 것이다. 이렇게 하기 위해서는 겹쳐지는 각 칸의 색이 같아야 하고, 한번 겹치면 그 두께 또한 합쳐진다. 어떤 칸의 색을 바꿀 수 있는데, 칸의 색을 바꾸기 위해서 드는 비용은 칸의 두께이다. 만약 겹치는 연산을 반복하다, 전체 배열의 길이가 2가 되면 종료한다. 이제, $M$개의 색에 대해 각각 최종 상..

문제 https://oj.uz/problem/view/JOI19_ho_t5 문제 보기 - Unique Cities (JOI19_ho_t5) :: oj.uz 문제 보기 - Unique Cities (JOI19_ho_t5) oj.uz 트리가 주어지고, 각 정점에 색이 칠해져 있을 때, 정점 $x$에 대한 unique한 정점 $y$를 다음과 같이 정의한다. $x$와 $y$의 거리가 $d$일 때 $x$에서 거리가 $d$인 $y$가 아닌 다른 정점 $z$가 존재하지 않는다. 각 정점에 대해, unique한 정점들의 서로 다른 색들의 개수를 구해야 한다. $M=dep-H[now]) cnt[V.back().second]--, V.pop_back(); if(chk[now]) ans[now]=V.size(); } els..

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..