kth990303의 코딩 블로그

알고리즘 스터디에서 나온 문제이다. 코드포스와 형식이 비슷해보여서 코포 연습 겸 블로그에 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/16288 16288번: Passport Control 입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 N 과 k 가 주어진다. N은 입국 승객의 수이며 k는 여권 심사 창구의 수이다. 단, 2 ≤ k ≤ N ≤ 100 이다. 그리고 두 번째 줄에는 승객이 입 www.acmicpc.net 문제가 잘 이해가 안돼서 [3, 1, 2]의 경우는 언제 가능한지 궁금했는데, Q1 (첫번째 통로)에 1, 2 / Q2에 3을 이동시킨 후에 출구로는 2번째 통로에서부터 나오게 하면 된다. 의식의 흐름 및 해설 이민을 가려 ..

대망의 UCPC 2022 본선날이 찾아왔다! 이번 UCPC 본선은 오프라인으로 진행됐기 때문에 더더욱 기대되는 순간이었다. 예선에 비해 본선은 진또배기 CP 고인물들이 나오는 대회라, 이번 대회는 꼴찌만 안해도 선방이라고 생각했다ㅋㅋ 나중에 2~3년 후에는 우리도 제대로 준비할 수 있는 대회가 되길 바라며, 결과부터 먼저 작성해보겠다. H, J, K, L 4솔로 41등이라는 꽤 괜찮은 성적을 얻었다. 목표가 본선 진출이었기 때문에, 4솔한 것 자체로도 만족스러웠다 ㅎㅎ 난 거의 한 게 없고 (오히려 J번 6맞왜틀 패널티를 선사함으로써 독이 된 것 같다) 팀원들이 너무 잘해준 덕분인 듯하다. 대회 후기를 가는 길부터 해서, 문제 푸는 과정, 대회를 마치고 난 후까지 차례대로 쭉 써보도록 하겠다~ 대회 시작..

UCPC 2022 예선에 출전했다! 이번에는 현재 건국대 솔브드 기준 1등이자, 코포의 왕이신 백준 핸들명 riroan님, 항상 백준 대회에서 우수한 성적을 거두신 건국대 컴공 에이스 백준 핸들명 aru0504님이랑 함께 참여했다. 우리 셋 다 건대생이기 때문에 '일감호는우리가지킨다' 라는 팀명으로 출전했으며, riroan님이 건덕이, aru0504님이 건구스, 내가 만쥬(건대 대표 귀여운 고양이이다^^) 라는 팀원명으로 출전했다. 목표는 본선 진출이다. A, B, E, F, J를 해결함으로써 5솔을 하였다! 만족스러운 성적이지만, 5솔 이상 한 팀이 꽤 많을 것으로 예상돼서 본선 진출 여부는 어떻게 될 지 모르겠다 ㅎㅎ... ㅜㅜ 학교 1등 팀 추가선발 15팀 이내에 해당돼서 추가선발이 되거나, 아니면..

감각 유지 겸 찾아본 문제. 많은 사람들이 풀었는데, 나는 안풀었길래 한 번 시도해보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 의식의 흐름 및 해설 매 초마다 자두를 가져가느냐, 안 가져가느냐에 따라 상태가 달라진다. 만약 같은 초에서 현재 움직인 횟수가 같은 경우, 그리고 위치가 같은 경우는 메모이제이션이 가능한 때이므로 dp로 풀 수 있다. 애초에 생긴 거부터가 dp처럼 생겼다. d[t][cnt][now]: 현재 t..

백준 초급스터디에 과제로 내준 문제인데, 생각보다 어려워보이는 문제여서 한 번 풀어보았다. KOI (정보올림피아드) 2018 고등부 2번 문제이기도 하다. 일단 비주얼부터 한 번 감상해보자. 비주얼이 거의 수능수학 문제를 뺨친다. 문제는 아래와 같다. https://www.acmicpc.net/problem/15976 15976번: XCorr $ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다. www.acmicpc.net 문제가 조금 헷갈릴 수 있는데, 입력에 주어지지 않은 xi, yi는 0이라고 생각하면 된다. 의식의 흐름 및 해설 우리가 구하려는 것을 다시 한 번 살펴보자. 으... 정말 비주얼이 끔찍하다. 일단 a..

PS 단톡방에서 추천받은 문제. (이거 왜 골드2..? 꽤나 어려웠다.) 문제는 아래와 같다. https://www.acmicpc.net/problem/14578 14578번: 영훈이의 색칠공부 영훈이가 색칠 할 수 있는 모든 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오. www.acmicpc.net 의식의 흐름 및 해설 처음에는 b, r을 놓을 수 있는 경우의 수 nC2로 접근하는데 방법이 잘 생각나지 않았다. 2*2부터 순서대로 도형을 그리면 생각나는 dp식이 있지 않을까 접근해보았는데, 오히려 2*2에서 가능했던 경우의 수가 3*3으로 확장되는 경우가 한 가지도 없었다. (눈치빠른 사람이라면 여기서 무언가 눈치챘을 수도 있다.) 좀 더 고민해보다가, 색이 어차피 두 가지뿐이므로 ..

알고리즘 중급 스터디에서 스프라그-그런디 정리를 공부한 후에 푼 문제이다. 정말 어렵다고 생각되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/16889 16889번: 중복 없는 님 게임 구사과와 큐브러버가 님 게임을 하려고 한다. 님 게임은 돌 더미 N개를 이용하며, i번째 돌 더미에 있는 돌의 개수는 Ai개이다. 두 사람은 턴을 번걸아 가지면서, 게임을 진행한다. 각 턴은 돌 더 www.acmicpc.net 의식의 흐름 및 해설 선공, 후공이 나누어져 있다. 그리고 두 플레이어는 항상 최선을 다하며, 돌이 몇 개 남아있는지 모두에게 공개되어 있다. 따라서 impartial game에 속하고, 돌 더미가 여러 개이므로 스프라그-그런디 정리를 이용할 수 있다. 이..

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

알고리즘 중급 스터디에서 과제로 해결해야 했던 문제. 포인트를 놓쳐 생각보다 굉장히 많이 삽질했다. 문제는 아래와 같다. https://www.acmicpc.net/problem/24520 24520번: Meet In The Middle 첫 번째 줄에 마을의 수 $N$, 약속의 수 $K$가 주어진다. $(1 \le N, K \le 100\,000)$ 이어지는 줄부터 $N-1$개의 줄에 도로 정보를 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $u$번 마을과 $v$번 마을 사이에 www.acmicpc.net 의식의 흐름 및 해설 N이 10만이기 때문에 DFS O(N)으로 모든 노드를 훑으면 시간초과이다. 따라서 특정 노드만 확인해주면 되는데, 정점들 사이의 거리는 LCA로 O(logn)에 구할 ..

추천받은 문제 중 하나. 입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/15816 15816번: 퀘스트 중인 모험가 첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q www.acmicpc.net 의식의 흐름 및 해설 수의 범위가 굉장히 크기 때문에 O(N^2) 이상의 시간복잡도 풀이는 불가능하며, 입력받는 퀘스트 범위가 -10억 ~ 10억인 점, 요청으로 추가되는 퀘스트 개..