PS 일지

https://www.acmicpc.net/problem/1176 1176번: 섞기 첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다. www.acmicpc.net 문제 요약 학생 $N$명이 줄을 서야 한다. 각 학생은 자신과 이웃한 모든 학생과 키의 차이가 $K$보다 크도록 줄을 서야 할 때, 줄을 서는 경우의 수를 구하는 문제이다. 문제 해결 $N$의 제한 $1 \le N \le 16$에 주목하자. bitmask dp가 딱 떠오르는 제한이다. 다음과 같이 식을 세워보자. $dp[i][j] = $지금까지 줄을 선 학생들의 집합이 이진수 $..

https://www.acmicpc.net/problem/24502 24502번: blobsad 채완이와 주환이가 이 일을 마칠 수 있는 최소 시간을 초 단위로 출력한다. 만약, 마칠 수 없다면 blobsad를 출력한다. www.acmicpc.net 문제 요약 길이 $N$인 수열 $A$와 양의 정수 $K$가 주어진다. 이 수열에 작업을 할 수 있다. 어떤 $i$에 대해, $A_i$를 1 줄이고 $A_{i-1}$ 혹은 $A_{i+1}$을 1 올린다. 모든 $i$에 대해 $A_i$가 $K$의 배수가 되도록 만들 때, 작업 횟수의 최솟값을 구하는 문제이다. 문제 해결 문제 $A_i$가 $K$의 배수인가를 결정짓는 요소는 $A_i \bmod{K}$이다. 따라서, 주어진 모든 $A_i$를 $A_i \bmod{K}..

https://www.acmicpc.net/problem/9015 9015번: 정사각형 각 테스트 케이스마다 가장 큰 정사각형의 넓이를 한 줄에 하나씩 출력한다. 단, 정사각형이 없는 경우 0을 출력한다. www.acmicpc.net 문제 요약 평면 위에 $N$개의 점이 주어졌을 때, 가장 큰 정사각형의 넓이를 구하는 문제이다. 문제 해결 어떠한 두 점 $P, Q$를 골랐을 때, 그 두 점을 이은 선분을 변으로 갖는 정사각형이 있는지 알 수 있을까? 그 두 점의 $x$좌표 변화량과 $y$좌표 변화량을 각각 $dx, dy$라고 하자. $P, Q$를 $(dx, -dy)$만큼 대칭이동한 점이 둘 다 존재한다면 정사각형이 된다. 이렇게 만들어진 사각형은 모두 변의 길이가 같고, 네 각이 항상 직각이 되기 때문에..

https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net 문제 요약 2차원 격자판이 주어지고, 각 칸에는 정수가 주어진다. 칸에서 상하좌우로 이동할 수 있으며 한 번의 이동에는 $T$의 시간이 소모된다. 이동을 3번 하고 나면, 풀을 먹어야 해서(?) 현재 칸에 쓰여있는 정수만큼의 시간이 더 걸린다. $(1,1)$에서 $(N,N)$으로 이동하는데 걸리는 최소 시간을 구하는 문제이다. 문제 해결 state를 구성하는 요소는 크게 세 가지..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 문제 요약 건물을 정점으로 본 방향그래프가 주어진다. 각 건물은 건설하거나 파괴될 수 있다. (중복 건설도 가능하다.)건물들 사이의 관계를 나타내는 방향 간선이 주어진다. 간선 $X \rightarrow Y$는 건물 $X$가 건설된 상태여야 건물 $Y$가 건설될 수 있다는 의미이다.$K$개의 작업이 주어지며, 각 작업은 건물 $a$를 건설하거나 파괴하는 것이다.이 ..

https://www.acmicpc.net/problem/25685 25685번: 좋은 노드 집합 찾기 Alice와 Bob은 트리를 이용한 놀이를 즐겨한다. n개의 노드를 가진 트리 가 있고 노드는 편의상 번호가 1부터 n까지 붙어있다고 하자. i번 노드의 부모 노드는 p[i] 라 하고, 루트 노드의 경우 p[i] = 0 www.acmicpc.net 문제 요약 정점에 $1$부터 $N$까지 번호가 부여된 루트 있는 트리에서, "좋은 노드 집합"은 이 트리의 노드의 부분집합 $S$이면서 아래 조건을 모두 만족하는 집합으로 정의한다. 어떤 노드 $x$가 $S$에 속해있다면 $x$와 연결된 노드들은 $S$에 속하지 않는다. 어떤 노드 $x$가 $S$에 속하지 않았다면 $x$의 자식 노드들 중 최소 하나의 노드는..

Codeforces Round 914 (Div. 2)에 참가했다. 요즘 시간대가 안 맞아서 참여하지 못했었는데, 1600점을 달성하겠다는 강한 의지를 가지고 드디어 참가했다. 이번에도 3솔따리인가 싶었는데 운 좋게 3솔은 면했다. A - Forked! (00:09) 변형 나이트가 $(a, b)$만큼의 칸을 움직일 수 있을 때, 이동 한 번으로 두 좌표에 모두 도달 가능한 칸의 개수를 세는 문제다. map으로 구현했는데, $a = b$인 경우를 빼느라 구현하는데 시간이 오래 걸렸다. B - Collecting Game (00:19) 수들을 모두 최소 PQ에 넣고 하나씩 빼면서 해당 수로 가능한 최대 개수를 구해줬다. C - Array Game (00:31) 우선, $k \ge 3$인 경우에는 답이 무조건 ..

12/1 ~ 12/10에 푼 문제들입니다. 문제의 풀이가 포함되어있으니 유의하세요. 12/1 BOJ 1911 - 흙길 보수하기 Gold 5 #sorting #greedy 웅덩이들을 $x$좌표 기준 오름차순으로 정렬해놓고, 변수 $t$를 (마지막 널빤지가 덮고있는 끝 지점 +1)로 유지하며 관리하자. 어떤 웅덩이 $[S, E)$에 대해, 그 웅덩이를 모두 덮기 위해 필요한 널빤지 수는 다음과 같다. $\lfloor \dfrac{E - \max(t, S) - 1}{L} \rfloor + 1$ 단, 마지막 널빤지가 그 웅덩이 전체를 포함하는 경우는 예외다. BOJ 30037 - K-Words Problem Gold 3 #implementation #string 문장 하나를 getline으로 받아서 2번 규칙을..

11/21 ~ 11/30에 푼 문제들입니다. 문제의 풀이가 포함되어있으니 유의하세요. 11/22 BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) Platinum 4 #dfs #sweeping 깊이를 기준으로 스위핑을 하면 된다. $0 \le i \le j \le \log_2{N}$인 $i, j$에 대해, 깊이 $i$ 이상 $j$ 이하의 모든 점을 탐색하며 최대 연속합을 구하자. 이 스위핑+탐색이 문제에서 요구하는 직사각형을 그려보는 것에 해당한다. 연속합은 트리를 inorder 순서로 펴서 구해도 되는데, 본인은 금광 테크닉으로 구했다. BOJ 16877 - 핌버 Platinum 3 #sprague_grundy 스프라그-그런디 정리로 해결하..

Codeforces Round 910 (Div. 2)에 참가했다. 예상했던 것보다 훨씬 어려워서 놀랐다. 풀다가 벽에 막힌 느낌이 강하게 들었고, 문제도 얼마 풀지 못해서 처음으로 레이팅이 떨어질까 걱정했다. A - Milica and String 00:05 AC 항상 1회 이하의 연산으로 가능하다. B의 개수를 세서 $k$보다 클 때, 같을 때, 작을 때로 분류해서 처리하면 된다. B - Milena and Admirer 00:23 AC 어떤 수를 쪼갤 때, 어떻게 해야 최적인지의 여부는 뒤에 존재하는 수들에 따라 달라진다. 따라서, 뒤에서부터 본다는 접근은 자연스럽다. $a_i > a_{i+1}$인 $i$에 대해, $a_i$를 모두 $a_{i+1}$이하인 수들로 나눠야 한다. 이 때 수행해야 하는 연..