dlwocks31의 PS일기장

BOJ 5552 - 걷는 산타클로스 (P5) https://www.acmicpc.net/problem/5552 5552번: 걷는 산타클로스 첫째 줄에 모든 집에 케이크를 배달하는데 드는 최소 시간을 출력하고, 둘째 줄에 내려야하는 교차로의 위치를 출력한다. 만약, 그러한 교차로가 여러개라면, 가장 서쪽에 있는 교차로를 출력한 www.acmicpc.net 문제: 바둑판 모양의 도로가 있고, N개의 집이 교차로에 위치해 있고, 산타클로스가 도로만 이용해서 모든 집에 선물을 배달해야 한다. 임의의 시작점에서 시작할 수 있고, 마지막 집을 제외한 모든 집은 배달 후 다시 시작점으로 돌아와야 한다. 풀이: 더보기 마지막 집 또한 시작점으로 돌아와야 한다고 한번 문제를 바꿔서 생각해보자. 그러면 최적의 시작점은 (..

BOJ 1559 - 놀라운 미로 (P5) https://www.acmicpc.net/problem/1559 1559번: 놀라운 미로 입력 데이터는 여러 개의 테스트 케이스로 구성되어 있다. 각각의 입력은 두 정수 M, N(2 ≤ M, N ≤ 100)으로 시작하며, 다음 M개의 줄에는 초기에 문이 열린 방향을 나타내는 N, E, S, W중 하나의 문자 www.acmicpc.net 문제: M*N미로에서, 각 칸마다 한 방향으로 문이 열려있고 이 방향은 매 초 시계방향으로 회전한다. 1,1에서 시작해서 M,N까지 가면서 모든 보물상자를 모아야 한다. 풀이: 더보기 먼저, 보물상자의 개수가 최대 8개임으로 각 보물상자를 먹었는지 여부를 256 미만의 비트마스크로 표현할 수 있다. 따라서 "dist[r][c][b..

BOJ 2325 - 개코전쟁 (P5) 문제: 양방향 그래프가 주어지고, 이 그래프에서 1번 정점에서 N번 정점으로의 최단거리가 최대가 되도록 도로 하나를 파괴했을 때의 최단경로를 구하자. N N까지의 일반적인 최단경로를 찾고, 이 최단경로 위의 간선을 하나씩 뺀 상태에서 최단경로를 구한 후에 그 중 가장 큰 최단경로를 출력하면 문제를 풀 수 있다. 코드: http://boj.kr/210a1d3ec1d04851a8b1059749d6dae9 --- 이렇게 풀면 다익스트라를 최대 N번 돌리고, 다익스트라의 시간복잡도가 약 M + NlogM이기 때문에, 곱하면 O(NM)의 시간복잡도로 시간초과가 난다고 생각할 수 있다. 다만 이 문제는 시간초과가 나지 않고 백준에서 100ms 내로 풀이가 돌고, 로컬에서 돌려본..

이번주는 앞 3문제만 풀었다. 나머지 두 문제는 어려웠다. BOJ 5551 - 쇼핑몰 (P5) https://www.acmicpc.net/problem/5551 문제: 무향 가중치 그래프가 주어지고, N개의 노드 중 K개는 쇼핑몰이다. 쇼핑몰에서 최단경로로 가장 멀리 떨어진 지점을 구하는데, 이때 지점은 노드뿐만이 아니라 간선 위의 어느 한 점이 될 수도 있다. 가장 멀리 떨어져 있는 지점이 얼마나 멀리 있는지 구하면 된다. 풀이: 더보기 일단 그냥 평범하게 노드까지의 최단경로를 구한다. 그 후에, 각 간선을 보면서 간선 위에서 가장 거리가 먼 지점은 어디인지를 따로 구해주면 된다. 예를 들어서 (u, v)를 연결하는 가중치 w의 간선이 있는데, dist[u] = 10, dist[v] = 13, w = ..

P5 - 등산 마니아 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 문제: 트리가 주어지고, 어떤 두 노드 사이의 “다양성”을 두 노드 사이의 트리 루트를 거치는 최단경로로 정의한다. 모든 가능한 노드 쌍의 다양성의 총 합을 계산하자. 풀이: 더보기 각 간선이 최종 답에 공헌하는 값을 구하는 법을 생각해보자. 즉, 각 간선에 대해 해당 간선을 최단경로에서 거치는 노드 쌍 개수를 세는 것이다. 해당 값은 간선 아래에 있는 subtree의 ..

P5 - 안대 낀 스피드러너 https://www.acmicpc.net/problem/14451 14451번: 안대 낀 스피드러너 "전진, 우회전, 전진, 전진, 좌회전, 전진, 좌회전, 전진, 전진"의 순서를 따르면 6초 또는 9초만에 도착할 수 있다. www.acmicpc.net 문제: N*N 격자에 각 칸은 비어 있거나 장애물이 있다. 왼쪽 아래 칸에서 시작해서 오른쪽 위까지 가야 하는데, 시작할 때 보고 있는 방향은 모른다. "전진", "좌회전", "우회전”을 최소 횟수만큼 사용해서 항상 목적지에 도달하는 방법을 찾아라. 풀이: 더보기 처음에 시작 가능한 상태가 두 가지 있고, 어떤 입력 순서가 주어졌을 때 1번 시작상태와 2번 시작상태가 위치한 곳은 확정적으로 구할 수 있다. 즉, 상태를 (1번..

P5 - 붕어빵타이쿤 https://www.acmicpc.net/problem/1704 1704번: 붕어빵타이쿤 첫째 줄에는 격자의 세로, 가로 크기를 나타내는 두 정수 M과 N이 주어진다. 두 번째부터 M+1번째 줄까지 N개의 0 또는 1의 숫자가 주어지는데 0은 현재 앞면이 위로 보이는 붕어빵이고 1은 현재 앞 www.acmicpc.net 문제: boolean 2D array가 주어지고, 한 점을 누르면 그 점과 상하좌우 4개 점의 값이 같이 반전된다. 점을 최소한으로 누르면서 배열을 모두 0으로 만드는 방법을 찾자. 풀이: 더보기 가장 위 행의 누르기 배치를 고정했다고 하자. 해당 배치로 인해서 가장 위 행의 배열 값이 1이 된 경우, 이를 보정할 수 있는 방법은 첫번째 행에서 1인 열에 해당하는 ..

같이 PS하는 친구들과 주마다 P5 - P1 난이도의 문제 각 하나씩 푸는 것을 목표로 재활훈련 중이다. P5 - 초고속철도 https://www.acmicpc.net/problem/2543 2543번: 초고속철도 첫째 줄에 문제의 조건을 만족하면서 처리장치를 부착할 수 있는 경우의 수를 출력한다. 만약 경우의 수가 20,070,713 이상일 때에는 20,070,713으로 나눈 나머지를 출력한다. 또한 계산 도중 오버플 www.acmicpc.net 문제: [l, r] 구간 N개가 주어지고, 이 중에서 subset을 고를 때, 겹치는 구간 pair라면 둘 중 하나는 subset에 포함해야 하는 제한이 있다. 가능한 모든 subset의 개수를 구하는 문제. 풀이: 더보기 이미 입력된 구간의 일부만 보고 답을..