본문 바로가기

백준

 (223)
백준 1937 - 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다음 dp 테이블을 세운다. dp[i][j] := 좌표 (i, j)에서 시작했을 때 가질 수 있는 최장 경로의 길이 각 좌표마다 가질 수 있는 최장 경로를 DFS로 검색하면 $O(V^{2}E)$가 되어 시간 초과를 받게 된다. 이를 $O(V^{2})$로 줄여보자. 각 정점마다 DFS를 수행하면서 거쳐간 정점에 저장한 지역 최장 경로는 일단 저장한다. 그리고 이미 거쳐간 정점에 대해서는 ..
[ICPC] 백준 11066 - 파일 합치기 https://www.acmicpc.net/problem/11066 다음 DP 테이블을 세운다. dp[i][j] := i번째부터 j번째 파일까지 합치는 최소 비용 4중 반복문으로 i번째 책을 시작으로 j + 1개의 연속된 책을 합치려고 하는데 pivot이 m번째 책일 때 양 옆의 책들을 합치는 비용을 계산하면서 테이블을 채우는 방법을 생각할 수 있다. 다만 연속된 책을 합치는 과정을 반복문마다 수행하면 시간 초과를 받을 위험이 있다. 누적합으로 파일을 합치는 비용을 미리 계산하면 일부 연속된 책을 합치는 비용을 $O(1)$의 시간 복잡도로 처리할 수 있으므로 3중 반복문으로 줄어든다. 주어지는 TC에 대해 3중 반복문으로 테이블을 채운 후 최소 비용을 출력하면 정답을 받을 수 있다. 전체 코드 더보기 #..
[KOI] 백준 2616 - 소형기관차 https://www.acmicpc.net/problem/2616 다음 dp 테이블을 생각한다. dp[i][j] := j번째 객차까지 소형 기관차 i개를 썼을 때 수송할 수 있는 최댓값 이렇게 했을 때 지금 객차부터 소형 기관차를 하나 사용하여 사람들을 수송했을 때, 지금 객차에서 소형 기관차를 사용하지 않고 다음 객차로 넘어갔을 때를 메모이제이션하여 문제를 풀 수 있다. 일일이 객차의 인원을 더하는 것은 무리이므로 객차별 인원을 누적합으로 관리하면 제한 시간 내에 정답을 받을 수 있다. 전체 코드 더보기 #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include u..
백준 1525 - 퍼즐 https://www.acmicpc.net/problem/1525 힌트 더보기 필요한 것: string 가능한 경우의 수: 9! 풀이 더보기 한 군데가 비어있는 퍼즐을 오름차순으로 배치하는 최소 횟수를 찾는 문제다. 비어있는 위치를 9라고 하면 1 2 3 4 5 6 7 8 9 의 형태로 퍼즐을 만드는 문제로 바꿀 수 있다. 그리고 이를 일렬로 나열하면 일직선 퍼즐을 123456789로 만드는 문제로 바꿀 수 있다. 퍼즐의 각 위치에서 이동할 수 있는 곳에 에지를 연결하면서 그래프 모델링을 하자. 그러면 현재 퍼즐의 상태가 주어졌을 때 숫자가 9인 노드는 연결된 노드의 숫자와 swap 할 수 있다는 의미가 된다. 123456789를 기준으로 9는 6, 8과 swap이 가능하다. 즉 9가 위치한 노드와 연결..
백준 1325 - 효율적인 해킹 https://www.acmicpc.net/problem/1325 A가 B를 신뢰한다는 것은 B가 A를 해킹할 수 있다는 뜻이며 B -> A 방향의 엣지가 주어지는 것으로 이해할 수 있다. 이 문제는 노드가 최대 10000개이며 우리는 감각적으로 PS를 할 때 1초에 1억 번(최근엔 2~3억) 번의 연산을 할 수 있음을 알고 있다. 즉 모든 노드에 대해 일일이 DFS/BFS를 수행하면 노드 한 개가 자기 자신을 포함하여 최대 10000개의 노드를 탐색하므로 $10^{4} \times 10^{4} = 10^{8}$번의 연산을 해야 하고 이는 5초라는 주어진 시간에 걸맞은 풀이가 된다. 각 노드마다 BFS혹은 DFS를 이용하여 최대로 해킹 가능한 컴퓨터가 몇 대인지 세주면 된다. 이렇게 구한 값은 2차원 선..

티스토리툴바