PS
-
JOI 2010/2011 2번 - 古本屋 (Books) 풀이PS/공부 2024. 12. 7. 15:51
[JOI 2010/2011 2번 - 古本屋 (Books)]https://www.acmicpc.net/problem/5550(AC 코드 - https://github.com/MongHwa/Algorithm/blob/main/Baekjoon/Books.cpp) 책의 장르 $G_i$가 10 이하임을 이용하여 봅시다.$val[g]$ - 장르가 $g$인 책의 가격이 모인 배열 이라고 할 때, [예제 입력 1]의 배열은 다음과 같습니다. $val[1] = \{14\}$$val[2] = \{13, 14, 11\}$$val[3] = \{12, 16\}$ 이때 장르2의 책 하나를 골라 가격의 최댓값을 만든다면 14를 고르는 게 최적이고, 책 두 개를 고른다면 14와 13을 고르는 것이 최적입니다. 따라서 각 장르에 따..
-
USACO 2014 January Contest Gold 3번 - Ski Course Rating 풀이PS/공부 2024. 10. 2. 12:01
(24.10.07 - AC 코드 전체를 추가하였습니다.) https://www.acmicpc.net/problem/9877 백준 알고리즘 태그에는 병렬 이분 탐색도 함께 붙어있습니다만, 이 글에서는 단순 분리 집합(유니온 파인드) 풀이를 제시합니다. 문제에서는 그래프를 $M$개의 행, $N$개의 열로 표현하고 있습니다만, 여기서는 $N$개의 행, $M$개의 열을 가진 그래프로 바꿔 설명하겠습니다. 또, 맨 왼쪽 위를 $0$행 $0$열로, 맨 오른쪽 아래를 $N-1$행 $M-1$열로 나타내도록 하겠습니다.이때 그래프의 $i$행 $j$열의 원소를 $i*M+j$번 노드라고 표현하면, 이 노드는 $i*M+j-1$번 노드(현재 노드의 왼쪽 노드), $i*M+j+1$번 노드(현재 노드의 오른쪽 노드), $(i-1..
-
제5회 고려대학교 MatKor Cup : 2024 Summer/Fall (Onsite) 후기PS/대회 2024. 9. 17. 00:38
[대회 전/예비소집]https://www.acmicpc.net/board/view/149113생각지도 못한 공지가 하나 올라왔었습니다. ps계에서는 귀하다고 할 수 있는 오프라인 대회 공지가 하나 올라온 것인데, 참여할지 말지가 조금 망설여졌습니다. Matkor Cup 대회 자체의 컨셉이 '수학'과 밀접하게 연관되어 있기 때문에, 수학을 그렇게 깊게 파고들어 공부해 본 적이 없는 저에겐 의미 없는 대회가 되진 아닐까 하는 생각이 들었기 때문입니다. 고민이 조금 되었는데, 그래도 참여해보기로 결정했습니다. 대회 컨셉과는 별개로 "오프라인 대회 경험 자체는 큰 의미가 있다"는 생각이 들기도 했고, 고려대도 한 번 구경해보고 싶어서 참가해 보기로 하였습니다. 본대회 전까지 본대회에 맞춰 특별한 연습을 하지는 ..
-
[SCPC] SCPC 2024 Round 2 (2차 예선) 후기 / 잡담PS/대회 2024. 8. 9. 00:15
*문제 풀이는 문제가 공개되고 풀이가 준비되는대로 올려보도록 하겠습니다. 작년과 다르게 2차 예선 발표가 늦어지면서 그 기간 동안 마음을 졸이며 지냈던 것 같습니다. 4번 문제를 끝내 만점을 받아놓고 총점이 1200점이 되면서 살짝 안심을 했었는데, 2차 예선이 끝나기 2~3시간 전에 결과를 확인해보니 4번이 꽤 많이 풀리면서 불안해지기 시작했었습니다. 본선을 노리는 입장에서 2차 예선이 끝나기 전까지 최선을 다해야 하는 게 맞았지만 5번 문제의 풀이가 전혀 떠오르지 않기도 했고, 4솔이면 그래도 본선에 갈 수 있지 않을까 하는 안일한 생각 때문에 올해도 역시 SCPC 본선에는 참가할 수 없게 되었습니다. 구현량이 굉장히 많은 셋이었습니다. 특히 4번은 짜면서도 이게 맞나 하는 생각이었는데, 다행히도 8..
-
UCPC 2024 예선 후기PS/대회 2024. 7. 16. 12:01
(2024.08.21 - 예선 스코어보드 링크를 추가하였습니다.) 벌써 세 번째 UCPC입니다. 저에게 있어서 저번 두 UCPC와 비교했을 때 이번 UCPC는 두 가지 다른 점들이 있었습니다. 하나는 팀원 구성이 바뀌었다는 점과, 또 하나는 처음으로 팀단위 연습을 진행해보았다는 점인데요. 그런 만큼 개인적으로는 올해 가장 의미있는 대회가 아닐까 싶은데, 막상 대회가 가까워지면 가까워질수록 자의 반 타의 반으로 ps 연습에 손을 놓은 것 같아 그게 좀 마음에 걸리네요 ㅠ 그간 있었던 팀연습들입니다. #1 #2 #3 #4(7월 7일에 진행했던 5번째 팀연습은 나중에 기회가 되면 올려보도록 하겠습니다.) (UCPC 2024 예선 및 예비소집 문제 세트 - https://www.acmicpc.net/cate..
-
[SCPC] SCPC 2024 Round 1 (1차 예선) 후기PS/대회 2024. 7. 6. 15:50
모비스를 시작으로 ps에서 메이저라고 할 수 있는 대회가 하나 둘 열리고 있습니다. 저는 SCPC를 2022년부터 참가해왔는데, 훨씬 이전 연도들의 1차 예선들과 비교해봐도 이번 2024년도 1차 예선 문제들이 상당히 쉽게 나오지 않았나 하는 생각이 들었습니다. 그런 만큼 컷 또한 달라질 것 같은데, 보통 1차 컷이 [1번솔 + 2번긁]이지만 이번 1차 컷은 [1,2번솔 + 3번긁]으로 형성되지 않을까 싶네요. 여담으로 개인적인 체감 난이도가 2 < 1이었는데, 다른 분들은 어땠을지 모르겠습니다. 5번 풀태 제한이 N
-
UCPC 팀연습 #4PS/Virtual Contest 2024. 6. 30. 10:26
(24.06.23 연습 기록입니다.)이번 연습 기록 글이 조금 늦었네요. 전역할 때가 다가오면 다가올수록 왜 더 바빠지는지 모르겠습니다 ㅠ 이번 연습 또한 저번처럼 3주 텀을 두고 진행되었는데, 저번과 달리 3주 동안 "6문제 디펜스" 같이 특별한 걸 하지는 않고 각자 개인 기량 올리기에만 집중하였습니다. 특별한 이유가 있어서는 아니고, 그냥 제가 많이 바빴어서.. ㅠㅠ 이번 문제셋은 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2022 Summer)로, 총 13문제인데다가 원래 대회 시간이 5시간인 관계로 10문제를 랜덤으로 뽑고 3시간으로 개량하여 연습을 준비하였습니다. D번(백준 25560번 - 포탈)이 언레가 되어 있어서 D번을 제외하고 랜덤으로 10문제를 뽑았는데..
-
UCPC 팀연습 #3PS/Virtual Contest 2024. 6. 6. 10:41
(24.06.02 연습 기록입니다.) 두 번째 팀연습 2주 후는 제 세 번째 휴가 기간이랑 겹치는데, 이 기간에 일정들이 좀 있어서 부득이하게 한 주를 더 미루게 되었습니다. 3주 동안 무엇을 하면 좋을까 생각하다가 저번 팀연습 결과를 바탕으로 매일 랜덤 6문제를 각자 풀어보기로 하였습니다. 중요한 승부처가 될 골드 상위 ~ 플레 문제에 익숙해지기 위해 골드3 ~ 플레3에서 각각 한 문제씩 랜덤으로 뽑아 6문제 세트를 구성하여 그룹 문제집에 올려두었습니다. 디펜스도 좋지만 단기간 실력 향상이 가장 중요한 문제이기 때문에 "해설을 봐도 좋으니 6문제는 꼭 해결을 하고 넘어가자"라고 팀원 분들에게 부탁드렸습니다. 그 결과는.. 이것저것 일이 겹쳐 문제집을 만들지 못하는 때도 있었고, 특히 후반부로 갈수록 문..