$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

알고리즘 문제풀이/BOJ

(20)
BOJ 13361 최고인 대장장이 토르비욘 난이도 : Solved.ac 기준 다이아 5 출처 : ICPC NWERC Regional, Nordic Collegiate Programming Contest [NCPC] 2016 H 1. 문제 설명 직사각형 $n$ 개가 주어진다. 각각의 두 변의 길이는 $a_i, b_i$ 이고, 이걸 적당히 돌려서 $n$개를 위로 쌓으려고 한다. 다음 조건을 만족해야 한다. - 각 직사각형의 '너비' 는 Strictly 감소 수열을 이뤄야 한다. - 가능한 경우 중 '높이' 가 최대한 커야 한다. 2. 풀이 굉장히 중요한 발상이 있는데, 이 발상을 처음 떠올리기는 많이 힘든 것 같다. 비슷한 문제를 어디선가 누가 말해줘서 이런 생각을 본적이 있는데 출처를 모르겠다. :( 직사각형이 가진 두 숫자 $a_i$ 와 $b_i..
BOJ 10847, APIO 2015 2 - Jakarta Skyscraper 출처 : 2015 Asia-Pacific Informatics Olympiad Problem 2 백준 번역명 "자카르타의 마천루" 난이도 : Diamond 3 1. 문제 설명 0번부터 $m-1$ 번까지의 번호를 가진 "도게" 가 있고, 이 도게들은 1 시간 만에 $+p$ 또는 $-p$ 만큼씩 점프할 수 있다. 도게끼리 만나면 소식을 전달할 수 있고, 소식을 이미 전달받은 도게만 움직일 수 있다. 1번 도게가 소식을 전달받는 최단 시간을 찾는 문제. 2. 풀이 설명 [36점, 57점 풀이 : Dijkstra] 최단 시간 (가중치가 주어질 때, 최단 경로)를 찾는 문제이고, 음수 간선이 없으며, $n \leq 30,000$개의 빌딩을 오가야 한다는 점에서 다익스트라 알고리즘을 이용해 보자는 생각을 할 수 있..
BOJ 15310 아티스트 출처 : 경기과학고 나는 코더다 2017 송년대회 F번 난이도 : Solved AC 기준 Diamond II 내가 왜 이걸 이렇게 풀었지... 이 모든게 해시코드 후유증이다. :blobcry: 1. 문제 설명 문제의 지문 자체는 별로 길지 않지만, 요약하면 다음과 같다. $(w_i, h_i)$ 의 정보를 갖는 '그림' 이 $n$ 개 주어진다. 이 '그림' 들 중 $k$ 개를 고를 것이다. 고른 그림들을 $1, 2, \dots k$ 번이라고 할 때, $$\left(\sum_{i = 1}^{k} w_i \right) \left(\sum_{i = 1}^{k} h_i \right)$$ 이 값을 최대한 Minimize하고 싶다. 2. 풀이 먼저, 생각해 보면 총 $\binom{n}{k}$ 개의 가능한 그림 조합들..
BOJ 13558 등차수열의 개수 난이도 : ??? 이 문제 같은 경우에는, 굉장히 어려운 (그리고 재밌는) 정해와, 그럼에도 불구하고 솔브드 난이도가 골드 3이 되어버린 이상한 스토리가 있다. 그래서 난이도는 ??? 인데, 정해를 기준으로 생각한다면 최소 다이아 급의 문제이고, 그냥 뚫을 생각이라면 골드5? 골드5정도면 충분한것 같다. 1. 문제 설명 길이가 $N$ 인 수열 $A_1, \dots A_n$ 에 대하여, $A_i, A_j, A_k$ 가 등차수열이 되는 $(i, j, k)$ (순서 지켜야 한다) 순서쌍의 개수를 찾는 문제이다. 수열의 길이는 10만, 각 수는 3만 이하. 2. 풀이 2-1. Multiset에 대해 생각하기 먼저, 이 문제가 왜 망했는지(...) 의 이야기를 하기 전에, 복잡도가 실제로 낮은 풀이에 대해 생각해..
BOJ 14347 / 14346 Radioactive Islands 난이도 : Solved AC 기준 루비 3 (Large), 루비 5 (Small) 출처 : Google CodeJam World Final 2016 내가 백준에 제출한 문제중에 가장 어려웠던 것 같다. 미적분학 II 책을 끼고 열심히 띵킹해서 풀었는데, 푸는 과정에서 잠시 백준 채점 서버가 멈추고 (내 코드가 5분 동안 돌아서 그런게 아닐까 싶은 정황이 있고, 완전히 그것때문은 아니라도 상당부분 기여한건 맞는거 같다. :cry:) 여러 일이 있었지만 아무튼 252초의 시간을 쓰면서 맞았다. 우웩;;; 먼저 14346 Small을 기준으로 풀이를 작성하고, 14347을 위해 필요한 관찰만 더 소개하는 것으로 하자. 1. 문제 설명 $(-10, a)$ 에서 보트가 출발하고, 목적지 $(10, b)$ 로 가려..
BOJ 16709 Congruence Equation 난이도 : Solved.ac 기준 다이아 3 출처 : 경기과학고 2018 송년대회 C번 1. 문제 설명 $10^{15}$ 정도의 큰 소수 $p$ 가 주어지고, $a^b \equiv b^a (\mod p)$ 를 만족하는 자연수 $1 \leq a, b \leq p(p-1)$ 순서쌍 $(a, b)$ 의 개수를 구하는 문제. 2. 풀이 풀이의 수식 전개 과정이 상당히 복잡하고 요구하는 지식의 허들이 높은 대신, 코딩이 상대적으로 쉽다. 종이에 엄청 써 보고 나면 컴퓨터 잡고 나서는 금방 풀 수 있는 문제. 먼저, $a$ 와 $b$ 가 모두 $p$ 의 배수인 경우에는, $a^b$ 와 $b^a$ 가 모두 $\mod p$ 에 대해서 0이 되므로 주어진 조건을 만족한다. 이러한 경우는 주어진 범위 안에 $(p-1)^2..
BOJ 12728 n제곱 계산 / 12925 Numbers 난이도 : Solved ac 기준 다이아 5 (개인적으로는 플 1 정도라고 생각한다.) 출처 : Google Code Jam 2008 Round 1A, C번 두 문제는 완전히 같은 문제로, 잘 모르지만 과거 번역 과정에서 문제가 중복된 것 같은데 어째서인지 사라지지 않았다. 세부 조건 등에서도 아무런 차이가 없다. 이 문제에서 제한이 작은 small 버전은 BOJ 12727번이다. 1. 문제 설명 $(3 + \sqrt{5})^n$ 의 소수점 앞 세 자리를 계산해야 한다. 예를 들어, $(3 + \sqrt{5})^10$ 의 값은 대략 $15490047.9323...$ 이므로 047을 출력하면 된다. $n$이 작을 때는 직접 계산할 수 있지만, 수십억 정도의 $n$에 대한 답을 빠르고 정확하게 제시해야 한다..
BOJ 15745 Snow Boots 난이도 : Solved ac 기준 Platinum 5 출처 : USACO 2018 Feburary Contest Gold - Problem 1 1. 문제 설명 높이 배열 $A$ 와 쿼리 10만 개가 주어진다. 각 쿼리는 $s_i$ 와 $d_i$ 로 구성되어 있는데, $s_i$ 는 지나갈 수 있는 최대 높이를 의미하고, $d_i$ 는 건너뛸 수 있는 최대 점프 크기를 의미한다. 즉, $d_i$ 이하의 점프로 1번부터 $N$번까지 뛰어가는데, $s_i$ 보다 높은 점을 밟지 않고 갈 수 있는지 여부를 빠르게 판정해야 한다. 예를 들어, 높이 배열이 $\texttt{0 3 8 5 6 9 0 0}$ 이고, $s_i = 4, d_i = 3$ 이라면 지나갈 수 없다. 1번에서 시작해서 2번까지 가더라도 3, 4, ..