$$\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' 카테고리의 글 목록::::Gratus' Blog

"알고리즘 문제풀이/BOJ" 관련 글 20

BOJ 13361 최고인 대장장이 토르비욘
알고리즘 문제풀이/BOJ 2020. 4. 22. 12:41
난이도 : 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
알고리즘 문제풀이/BOJ 2020. 3. 18. 18:35
출처 : 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 아티스트
알고리즘 문제풀이/BOJ 2020. 3. 7. 18:45
출처 : 경기과학고 나는 코더다 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 등차수열의 개수
알고리즘 문제풀이/BOJ 2020. 2. 29. 02:10
난이도 : ??? 이 문제 같은 경우에는, 굉장히 어려운 (그리고 재밌는) 정해와, 그럼에도 불구하고 솔브드 난이도가 골드 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
알고리즘 문제풀이/BOJ 2020. 2. 4. 04:14
난이도 : Solved AC 기준 루비 3 (Large), 루비 5 (Small) 출처 : Google CodeJam World Final 2016 내가 백준에 제출한 문제중에 가장 어려웠던 것 같다. 미적분학 II 책을 끼고 열심히 띵킹해서 풀었는데, 푸는 과정에서 잠시 백준 채점 서버가 멈추고 (내 코드가 5분 동안 돌아서 그런게 아닐까 싶은 정황이 있고, 완전히 그것때문은 아니라도 상당부분 기여한건 맞는거 같다. :cry:) 여러 일이 있었지만 아무튼 252초의 시간을 쓰면서 맞았다. 우웩;;; 먼저 14346 Small을 기준으로 풀이를 작성하고, 14347을 위해 필요한 관찰만 더 소개하는 것으로 하자. 1. 문제 설명 $(-10, a)$ 에서 보트가 출발하고, 목적지 $(10, b)$ 로 가려..
admin

티스토리툴바