문제 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 이진탐색 문제였다. N의 범위가 크기 때문에 O(N^2)의 풀이로는 시간초과가 날 수 밖에 없다. 절단한 나무 길이의 합(_sum)을 집으로 가져가야 하는 나무의 길이(M)와 비교하여 포인터를 옮긴다. 이때, 합이 길이보다 작다면 right포인터를 mid-1로 줄여서 탐색의 범위를 줄인다. 반대로 크다면 left포인터를 mid+1로 옮긴 후, 현재 mid포인터가..
문제 www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 재밌어 보이는 문제라서 풀어보았다. 3중 for문을 이용해서 땅의 최소 높이(0)부터 최대 높이(256)까지 모두 검사해본다. 이때, B + sum(g[i][j]) // m*n을 X라 하면, 땅의 최대 높이는 min(256, X)이 된다. → B가 최대 6.4 × 10^7가 될 수 있기 때문에 X가 기하급수적으로 커질 수 있다! B: 인벤토리에서 가지고 있는 블록의 개수 sum(g[i][j]): 각..
문제 www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 연결 요소의 개수 문제와 상당히 유사한 문제였다. DFS로 풀 수 있는 기본적인 그래프 문제로, 인덱싱할 때만 주의하면 된다. 코드 import sys, collections sys.setrecursionlimit(10**6) def make_graph(n, p): g = collections.defaultdict(int) fo..
문제 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 음수 가중치가 주어졌기 때문에 벨만 포드 알고리즘을 사용했다. 나무위키에 나와있는 슈도 코드를 그대로 구현하면 된다. '시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.'라는 조건이 있는데, 말이 너무 어렵다. 쉽게 말해서 음수 사이클을 찾으라는 이야기다. 음수 사이클을 체크하는 부분만 넣어주면 문제없이 해결할 수 있..
문제 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 완전한 구현 문제다. 순열을 통해 모든 경우의 수를 구한 후, 연산으로 이루어진 순열을 큐에 담아 rotate 함수에 전달한다. 회전을 구현하는 과정은 조금 지저분하게 구현했다. 이때 좌측 상단의 좌표를 (ux, uy)로, 우측 하단의 좌표를 (lx, ly)로 두고 좌에서 우로, 상에서 하로 값을 덮어 씌웠다. 이를 위해 모서리의 값을 t1, t2, t3 변수에 담아두었..
