취미로PS하는사람

최근에 PS를 다시 하면서 뭘 풀어야 할지 모르겠다는 생각이 들었다. 둘러보다가 고등학교 친구가 만든 인생추천셋이 있길래 차근차근 풀어보려고 한다. https://dsstar.tistory.com/53 Journey to TST 문제 셋 공유 BOJ 그룹(https://www.acmicpc.net/group/16794)에서 2주 동안 총 44(+2) 문제의 연습 셋을 공유했다. 11일 간 매일 선발고사 난이도에 맞추어 4문제씩 셋을 만들었다. 모든 문제에서 얻어갈 내용이 있으며, 내 9 dsstar.tistory.com 내가 푼 순서대로 리뷰하려고 한다. 때문에 세터의 의도와는 다르게 대략 난이도 순이니 이 부분에 있어서 스포일러를 원치 않는다면 문제를 풀고 오기를 바란다. 약 4.5일간 푼 것 같다. ..

https://www.acmicpc.net/problem/17694 JOI spring camp 16/17 문제. 예전에 친구와 R&E 가서 얘기했던 문제다. 최근에 다시 잡고 생각을 하다가 어느 정도 풀만해 보이는 수열 문제로 바꿨는데, 그 이후 진전이 없다가 오늘 그림판에 열심히 그리면서 풀이를 찾아 풀었다. 뭔가 그리디적인 풀이가 있는 것으로 보이나 나는 $dp$ 경로를 최적화하는 방식으로 생각했다. 문제 $N$명의 사람이 각각 $T$초동안 타는 불꽃을 들고 서 있고, $K$번째 사람의 불꽃만이 시간 $0$에 타기 시작한다. 한 사람이 불꽃을 두 번 이상 태울 수는 없다. 0초에 $i$번째 사람은 $X_i$에 서 있고, $X_i \leq X_{i+1}, X_1=0$을 만족한다. 두 사람이 같은 좌표..

https://www.acmicpc.net/problem/9022 랜덤 icpc 플래 dp 뿌시기 하면서 나온 문제. 정렬에서 잘못해 몇번 틀리다가 맞았다. 이후 시간복잡도를 줄여보았다. [2022.06.16 추가] IOI 2016의 Alien에서 Alien Trick을 제외한 것과 거의 동일한 문제이다. 문제 평면에 여러 정수좌표 점들이 주어진다. x축 위의 여러 점을 중심으로 각 변이 x축과 45도 기울어진 정사각형들을 그려 모든 점들이 적어도 하나의 정사각형의 경계나 내부에 있게 할 것이다. 정사각형 면적 합의 최소는? 풀이 더보기 우선 $y_i

https://www.acmicpc.net/problem/19274 앳코더를 사랑하는 나에게는 정말 익숙한 이름인 Snuke좌가 나오는 문제다. 대학생을 대상으로 하는 러시아 캠프(페트로 뭐시기)에서 앳코더쪽 사람들이 낸 문제인 것 같았다. 그래서 그런지 문제 스타일도 앳코더 스타일 느낌이 강하다. 코딩 간단, 디스크립션 간단, 아이디어성. 문제 정점이 $N$개인 트리가 주어진다. 우리는 적당히 $K$개의 정점 $x_1, x_2, \cdots, x_K$를 선택하여 임의의 정점 $i$에 대해 $(d(x_1, i), d(x_2, i), \cdots, d(x_K, i))$가 모두 다르도록 할 것이다. 다시 말해, $K$개의 정점을 골라 각 정점들로부터의 거리 정보 벡터로부터 어떤 점인지 알아낼 수 있도록 $K..

https://www.acmicpc.net/problem/19833 간단한 수열에서의 문제. 앳코더 스타일 같아서 마음에 들었고 충분히 대회에도 나올만 한 문제라고 느꼈다. 다만 코딩미스라던지 생각을 깔끔히 정리하지 못해 시간이 꽤나 걸렸다.. 다른 사람들의 답안을 훑어보니, 나와 비슷하게 푼 사람도 있었고 스택(?)을 이용하여 푸는 방법도 있는 것 같았다. 성실한 사람이라면 둘 모두 알아보면 좋을 것 같다. 문제 수열$\{a_i\}$가 주어진다. 서로 겹치는 원소가 없는 두 구간의 최댓값이 같은 경우의 수(즉, 구간쌍의 개수)를 구하시오. 풀이 더보기 수열의 수들을 좌표압축하면 $[1, n]$의 숫자로만 이루어져있다고 봐도 무방하다. 이제 $a_k=x$인 $k$들을 순서대로 $v_{x,1}, v_{x,..