데구리 블로그

문제 링크 https://www.acmicpc.net/problem/15784 해당되는 칸을 기준으로 같은 행, 같은 열에 그 칸보다 높은 값을 가진 칸이 없는지 확인하면 된다. 행과 열에서 따로따로 확인하자. 정답 코드

문제 링크 https://www.acmicpc.net/problem/12888 간단해 보이니까 머리를 싸매고 잘 생각해보자.. 어... 음... 헷갈린다. 이럴땐 그림판으로 그림을 그려보면 된다. 와! 규칙을 찾았다! $i$가 홀수일 때 $d[i] = (d[i-1] - 1)*2 + 1 = d[i-1]*2 - 1$ $i$가 짝수일 때 $d[i] = d[i-1]*2 + 1$ 그대로 코드로 옮기면 된다. 단, $0 \leq n$이므로 $n = 0$인 경우도 구해줘야 한다. 답이 나올 수 있는 범위는 long long 범위인 것도 확인하자. 정답 코드

문제 링크 2018/07/26 추가내용.참고) post-order대신 pre-order로 순회 해도 같은 효과를 볼 수 있으며, 코드를 조금 더 편하게, 더 직관적으로 짤 수 있다. pre-order로 순회하는 코드는 여기를 참고하자. 1번 정점을 루트로 하는 트리가 주어지고, M개의 질의가 주어졌을 때 다음과 같은 명령을 실행한다. 1 x꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.2 x y꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y를 XOR함 . 얼핏 봐선 그냥 하면 되는거 아닌가 싶겠지만 범위가 굉장히 크다.정점의 수 N과 질의의 수 M에 대해$(1\leq N \leq 100,000)$, $(1\leq M \leq ..

문제 링크 https://www.acmicpc.net/problem/15781 헬멧과 조끼는 서로에게 영향을 주지 않는다. 따라서 헬멧 중 가장 높은 방어력을 가진 것과, 조끼 중 가장 높은 방어력을 가진 것을 골라 더해주면 된다. 정답 코드

문제 링크https://www.acmicpc.net/problem/15780 대충 계산해보자.구의 수 1 2 3 4 5 6 7 꽃는 수 1 1 2 2 3 3 4 구의 수를 $x$라 하면, 꽃을 수 있는 수는 $\frac{x + 1}{2}$ 이다. 정답 코드

문제 링크https://www.acmicpc.net/problem/5214 역들을 연결하는 하이퍼튜브가 있고, 각 하이퍼튜브가 서로 연결하는 역들이 주어질 때 1번 역에서 N번 역으로 가는데 방문하는 역의 개수의 최소값을 구해야 한다. 누가 봐도 BFS문제이지만 일반적인 방법처럼 연결된 역들을 모두 그래프로 이어버리면 메모리 초과를 받게 된다. 일반적인 방법대로 풀어보자.하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 $1 \leq K, M \leq 1,000$이다. 하이퍼튜브 하나당 정점끼리 $K^2$개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경우 $O(MK^2) = 1,000,000,000$개이다. 메모리가 터질 수밖에 없다. 중복된 간선을 여러번 연결했기 때문..

문제 링크 https://www.acmicpc.net/problem/1008 두 정수 A와 B를 받아 A/B를 출력하자. 절대/상대 오차를 $10^{-9}$까지 허용하기 때문에 정확한 답을 위해 소수 10자리까지 출력한다. 정답 코드

문제 링크 https://www.acmicpc.net/problem/1005 "모든 건물을 지을 수 없는 경우는 없다."라는 조건에서 주어진 그래프가 싸이클 없는 방향 그래프(DAG)라는 걸 알 수 있다. 건물을 짓는 순서가 정해져 있으므로 위상정렬로 해결할 수 있다. 단순 BFS로는 풀기 힘들다. 본문의 예제를 단계별로 살펴보자. $x$번 건물이 완성될 때까지의 총 시간을 $d[x]$으로 표현하겠다. 아직 완성 시간을 알 수 없는 건물은 0의 값을 가진다. $step\,0)$ 초기상태이다. $n$ 1 2 3 4 $d$ 0 0 0 0 $step\,1)$ 우선 1번 건물을 먼저 지을 수 있고, 10초가 걸린다. $n$ 1 2 3 4 $d$ 10 0 0 0 $step\,2)$ 2번과 3번을 동시에 지을 수 ..

문제 링크https://www.acmicpc.net/problem/1004 맞은 사람 목록을 보면 해당 풀이보다 더 간단한 풀이가 존재하는 것 같다. 어쨌든 내 경우엔 이렇게 풀었다. 좌표평면 위의 원(행성계)들이 주어지고 출발점과 도착점이 주어졌을 때, 출발점에서 도착점으로 가는 동안 원을 뚫고 가는 횟수를 최소화해야 한다.문제에서 "행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다."라는 조건을 주었기 때문에 쉽게 풀 수 있다. 풀이에 앞서 '점 $X$ 또는 원$X$가 원$C$에 포함된다'라는 말을 '$X$가 $C$의 경계에 걸치거나 교차하지 않으면서, $C$ 내부에 있는 상태' 라고 하겠다. 1) 출발점이나 도착점이 여러 개의 원에 포함된다면 그 원 중에서도 작은 원은 항상 큰 원에 포..

문제 링크 https://www.acmicpc.net/problem/1003 기본적인 피보나치 문제를 모르거나 시간초과가 문제라면 http://degurii.tistory.com/14?category=755814 를 참고하자. 기존의 피보나치 함수가 $$f(n) = f(n - 2) + f(n - 1)$$ 이므로 $n$일때 호출되는 0과 1의 개수를 $[$0의개수, 1의개수$]_n$ 로 표현해서 단순히 $[i, j]_n = [i, j]_{n - 2} + [i, j]_{n - 1}$ 처럼 쓸 수 있다. 이때, $[i, j] + [x, y] = [i + x, j + y]$로 정의한다. 정답 코드