반응형

PS/BOJ 85

[BOJ] 백준 16288. Passport Control

알고리즘 스터디에서 나온 문제이다. 코드포스와 형식이 비슷해보여서 코포 연습 겸 블로그에 포스팅해보려 한다. 문제는 아래와 같다. 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번째 통로에서부터 나오게 하면 된다. 의식의 흐름 및 해설 이민을 가려 ..

PS/BOJ 2022.08.12

[BOJ] 백준 2240. 자두나무 (Gold V)

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

PS/BOJ 2022.06.09

[BOJ] 백준 15976. XCorr (Gold III)

백준 초급스터디에 과제로 내준 문제인데, 생각보다 어려워보이는 문제여서 한 번 풀어보았다. 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/BOJ 2022.05.15

[BOJ] 백준 14578. 영훈이의 색칠공부 (Gold II)

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으로 확장되는 경우가 한 가지도 없었다. (눈치빠른 사람이라면 여기서 무언가 눈치챘을 수도 있다.) 좀 더 고민해보다가, 색이 어차피 두 가지뿐이므로 ..

PS/BOJ 2022.04.26

[BOJ] 백준 16889. 중복 없는 님 게임 (Platinum I)

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

PS/BOJ 2022.04.16

[BOJ] 백준 20191. 줄임말 (Gold II)

학교 채점현황을 둘러보다가 발견한 문제. 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 정도의 문제였..

PS/BOJ 2022.04.15

[BOJ] 백준 24520. Meet In The Middle (Platinum IV)

알고리즘 중급 스터디에서 과제로 해결해야 했던 문제. 포인트를 놓쳐 생각보다 굉장히 많이 삽질했다. 문제는 아래와 같다. 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)에 구할 ..

PS/BOJ 2022.03.25

[BOJ] 백준 15816. 퀘스트 중인 모험가 (Platinum IV)

추천받은 문제 중 하나. 입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제. 문제는 아래와 같다. 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억인 점, 요청으로 추가되는 퀘스트 개..

PS/BOJ 2022.03.12

[BOJ] 백준 14863. 서울에서 경산까지 (Gold IV)

추천받은 문제 중 하나. 문제는 아래와 같다. https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 의식의 흐름 및 해설 처음엔 평범한 knapsack인줄 알았는데, 생각해보니 자전거를 탈지, 도보로 갈지 선택을 해야되기 때문에 모든 경우를 선택하는 문제가 아니므로 knapsack dp가 아니었다. 따라서 top-down이든, bottom-up이든 시간복잡도 상 큰 차이가 없기 때문에 탑다운으로 풀었으며, N..

PS/BOJ 2022.03.12

[BOJ] 백준 1325. 효율적인 해킹 (Silver I)

스터디그룹 채점현황 둘러보다가 발견한 문제. 결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다. 문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1325 sync_with_stdio(0); cin>>n>>m; while(m--){ int a,b; cin>>a>>b; v[b].push_back(a); } int M=0; for(int j=1;j>a>>b; v[b]...

PS/BOJ 2022.02.24
반응형