PS
-
BOJ 18798. OR과 쿼리PS 2022. 9. 12. 17:01
https://www.acmicpc.net/problem/18798 18798번: OR과 쿼리 길이가 N인 수열 A1, A2, ..., AN과 음이 아닌 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 l r x : 모든 l ≤ i ≤ r에 대해, Ai를 Ai ∨ x로 바꾼다. (단, ∨는 bitwise OR 연산이 www.acmicpc.net 쿼리 문제이고, l, r 범위를 주고 하다 보니 자연스럽게 세그먼트 트리가 생각납니다. 쿼리 문제에서 세그먼트 트리가 유용한 이유는 특정 구간에 대한 연산을 O(구간의 크기)보다 작은 시간복잡도에 처리할 수 있는 경우가 많기 때문인데, 이 문제의 1번 쿼리는 그럴 방법이 없어보입니다. Bitwise OR 연산이라서 구간 내의 수마다 더..
-
BOJ 5470. 균형잡힌 직선형 정원 (DP X 풀이)PS 2022. 9. 6. 20:36
https://www.acmicpc.net/problem/5470 5470번: 균형잡힌 직선형 정원 람세스 2세가 전투에서 승리를 거두고 귀환했다. 그는 승리를 기리기 위해 웅장한 정원을 조성하기로 결심했다. 그래서 궁궐이 있는 Lubrr에서부터 시작해 Karnak 신전에 이르는 긴 길을 따라 식물 www.acmicpc.net DP로 쉽게? 플2가 쉬운지는 모르겠지만 하여튼 풀린다고 하는데 DP를 못해서 다르게 풀어봤습니다. 무언가가 오름차순으로 몇 번째에 있는지를 구할 때 자주 쓰는 방법이, 앞자리부터 보면서 자리별로 '건너뛴' 경우의 수를 세서 더하는 것입니다. 'ability'라는 단어가 사전에서 몇 번째에 있는지를 알고 싶다면, 먼저 aa로 시작하는 모든 단어의 수를 더하고, ab로 시작하는 단어..
-
BOJ 2664. 다각형의 확장PS 2022. 8. 29. 11:54
BOJ 2664. 다각형의 확장 2664번: 다각형의 확장 첫 번째 줄에 d가 주어지고 그 다음 줄에는 n이 주어진다. 그 다음 n개의 줄에 다각형을 나타내는 n개의 좌표가 주어진다. 여기서 1 ≤ d ≤ 500이고, 3 ≤ n ≤ 50이며, X, Y 좌표 값은 2000 이하의 자연 www.acmicpc.net 2년 전에 아주 고생하며 풀었던 문제인데, 당시 무슨 생각을 하면서 풀었는지 복기해보는 글입니다. 검은 배경의 그림은 2년 전 풀면서 직접 그렸던 그림입니다. 입력이 볼록 다각형인 경우를 생각해보면 아주 쉬워집니다. (가능한 볼록 다각형은 직사각형뿐이지만) 정확히는 볼록 다각형이 아니더라도, d-확장을 하는 과정에서 변들이 서로 만나서 '쌍소멸'할 가능성이 없는 경우도 똑같은 이유로 아주 쉽습니다..
-
2021 NYPC 예선 후기 + 풀이PS 2021. 8. 31. 22:00
지난 8월 26일 목요일, 8일간의 2021 NYPC 예선이 종료되었습니다. 작년에 이어 두 번째로 NYPC 예선에 참여하게 된 것이었는데, 작년은 대회의 존재를 종료 이틀 전에 알게 되어서 아쉬움이 많이 남았었고 제대로는 올해 처음 하게 되었네요. 사실 심심하니까 한 번 해봐야지~ 정도였는데 생각보다는 훨씬 열심히 한 것 같습니다. 3회차부터는 계속 이것만 붙들고 있었던 듯.. 결과 제 기준에서는 믿을 수 없을 정도로 좋은 결과지만 분위기를 보아하니 본선은 무리인가 봅니다. 그래도 못 풀 문제 풀고, 못 긁을 서브태스크도 긁은 것이 참 많아서 위의 사진만 보면 참 뿌듯합니다. 1년 사이에 많이 성장한 것 같다고 느껴지네요... 풀이 *풀이는 과하게 자세한 부분과 과하게 미흡한 부분이 많이 있을 수 있습..