mojo's Blog

문제 링크 => 11404번: 플로이드 (acmicpc.net) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Floyd-warshall 알고리즘을 이용한 문제이다. 문제 풀이순서는 다음과 같다. (d[x][y] = x에서 y까지 이동할 수 있는 최단 경로) 1. d[x][y] 의 값을 미리 세팅한다. (1) x = y 일 경우 : d[x][y] = 0 (자기 자신으로 가는 경우는 0) (2) x ≠ y 일 경우 : d[x][y] = INF (이동할 수 없는 경우를 INF 으로 마킹) 2. 인풋으로 주어진 x..

문제 링크 => 10251번: 운전 면허 시험 (acmicpc.net) 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 아무래도 여러번 recursion을 이용한 memoziation 기법을 이용해서 해결하려고 했으나 시간초과가 계속 뜬다. 그래서 4차원 배열을 설정하여 다음과 같이 해결하였다. dp(curX, curY, turn, direction) = (curX, curY) 에서 turn 번 회전하여 direction 방향을 바라볼 때의 최소 연료량 먼저 시작지점에서부터 오른쪽 방향, 아래쪽 방향으로 가는 것은 회전하는 것이..

문제 링크 => 11779번: 최소비용 구하기 2 (acmicpc.net) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 전형적인 다익스트라 문제이다. 다익스트라 알고리즘을 활용하여 최소거리를 구할 수 있어야 하며 동시에 경로까지 출력해야 하는 문제이다. 경로를 추적하기 위한 배열 trace 를 이용하였다. 시작 지점으로부터 다음 지점(next)까지의 최소 거리를 Distance[next] 라고 할 때 해당 값이 update 될 때마다 현재 위치(cur)에 대해서 trace[n..

문제 링크 => 23743번: 방탈출 (acmicpc.net) 23743번: 방탈출 첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으 www.acmicpc.net 방탈출 카페에는 1번부터 N번까지 총 N개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다. 방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 M개까지 설치할 수 있는데, i번째 워프는 ..

문제 링크 => 3648번: 아이돌 (acmicpc.net) 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 2-SAT 문제이다. 각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다. 두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다. 즉, 두 표 모두와 반대되는 결과가 나오면 투표 결과에 대해서 의심을 하게 되는데 이를 방지해야 한다. 예를 들어서 심사위원 X 가 1번째 참가자(A) 에게 찬성, 2번째 참가자(B) 에게 반대를 던졌다고 하자. 그렇다면 f(A, B) = A ..

문제 링크 => 1937번: 욕심쟁이 판다 (acmicpc.net) 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 어떠한 지점 (x, y) 에서 존재하는 대나무를 먹고 다음 지점(nextX, nextY) 으로 이동할 때, 다음 지점(nextX, nextY) 에 존재하는 대나무의 갯수가 (x, y) 지점에 있던 대나무의 갯수보다 클 경우 다음 지점으로 이동하여 대나무를 먹는다. 이렇게 판다가 이동하면서 대나무를 야무지게 먹을 수 있는 최대 거리를 구해야 한다. 알 수 ..