본문 바로가기

전체 글

 (5)
백준 23824번 서버 증축 문제 백준 23824번 서버 증축 풀이 정수 $k, a, n$이 주어진다. $(1 \le k \le 40;$ $1 \le a \le {10}^{6};$ $1 \le n \le {10}^{15})$ 중복집합 $A = \{\underbrace{2^0, 2^0, \cdots, 2^0}_{a\text{ times}}, \underbrace{2^1, 2^1, \cdots, 2^1}_{a\text{ times}}, \cdots, \underbrace{2^{k-1}, 2^{k-1}, \cdots, 2^{k-1}}_{a\text{ times}}\}$의 부분집합을 $B$라고 할 때 $\sum_{x \in B}{x}=n$인 $B$의 개수를 구해야 한다. 다음과 같은 생성함수 $F(x)$를 생각하자. $$ \begin{al..
수열의 합 2 출제 2022 SKKU 프로그래밍 대회 in 소프트의 밤에 출제했던 수열의 합 문제의 입력 제한을 $10^7$에서 $10^{14}$로 바꾼 수열의 합 2 문제를 출제했다. 대회 출제 후기에서 언급했듯이 수열의 합은 $\mathcal{O}\left(\sqrt{N}\right)$ 풀이를 생각하고 만든 문제였기 때문에 수열의 합 2를 개인적으로 출제하게 되었다. 기존 수열의 합의 풀이는 풀이 슬라이드에서 확인할 수 있다. 어떤 양의 정수 $d$가 $\sum_{i=1}^{N}{a_i}$에 몇 번 기여하는지 생각하면 $\sum_{i=1}^{N}{a_i}=\sum_{i=1}^{N}{\left(-1\right)^{i}\lfloor\frac{N}{i}\rfloor}$임을 알 수 있다. 이제 $\sum_{i=1}^{N}{\l..
2022 SKKU 프로그래밍 대회 in 소프트의 밤 출제 2022 SKKU 프로그래밍 대회 in 소프트의 밤에 문제를 출제했다 (대회 문제, 풀이 슬라이드). 이전에 SW마에스트로 제13기 알고리즘 대회에 문제를 출제한 적이 있어서 Polygon과 같은 도구는 사용해 본 적이 있었지만 백준에서 대회를 연 것은 처음이라 새로운 경험이었다. 내가 출제한 문제는 총 세 문제로 E. 수열의 합, J. 달나라에 사는 토끼와 우주에서 떨어지는 떡, K. 커모드 곰의 연어 사냥을 출제하였다. 출제 E. 수열의 합 대회에 간단한 수학 문제가 있으면 좋을 것 같아서 만든 문제이다. 아이디어를 얻기 위해 고등학교 수학 I 문제집을 살펴보다가 $a_n = \left(-1\right)^{d_1} + \left(-1\right)^{d_2} + \cdots + \left(-1\righ..
백준 8895번 막대 배치 1328번 고층 빌딩 이 글에서 다룰 문제는 백준 8895번 막대 배치와 1328번 고층 빌딩이다. 두 문제는 주어지는 입력의 범위 정도만 다르고 거의 같은 문제라고 볼 수 있다. 8895번 막대 배치 문제를 중점적으로 설명하고 1328번 고층 빌딩 문제는 차이점을 기준으로 간단히 언급하는 식으로 진행하겠다. 문제 https://www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근..
백준 1520번 내리막 길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 상하좌우로 이동 가능하고 높은 곳에서 낮은 곳으로만 이동이 가능할 때, 왼쪽 위 지점에서 오른쪽 아래 지점까지 이동하는 경우의 수를 구하는 문제입니다. 10164번과 유사하게 점화식을 세울 수 있지만, 위 또는 왼쪽으로도 이동할 수 있다는 점, 그리고 높은 곳에서 낮은 곳으로만 이동 가능하다는 점을 고려해 주어야 합니다. 우선 시작 지점을 (1, 1) 그리고 도착 지점을 (N, M)이라고 합..

티스토리툴바