목록백준 (205)
어흥
문제 링크: https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다. 지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한 www.acmicpc.net 1. 주의할 점 - 메모아이징을 사용한 DFS를 이용한다 (DP문제) 2. 구현 - Check[] 배열을 전..
문제 링크: https://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. 주의할 점 - 음의 가중치를 가지는 간선이 존재한다 -> 벨만포드 알고리즘 (다익스트라 알고리즘은 음의 가중치가 있으면 적용하지 못한다) - Int의 범위를 벗어날 수도 있기 때문에 (Dist의 값이) Long Long으로 설정하지 않으면 "출력초과"가 발생한다 2. 구현 - 2차 배열을 이용한 형태와 벡터에 간선을 담..
문제 링크: https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 1. 주의할 점 - MST 문제로, 프림 혹은 크루스칼 알고리즘에 대하여 알고 있어야 한다. 여기서는 크루스칼 사용 - X..
문제 링크: https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 문제 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다. 상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이 www.acmicpc.net 1. 주의할 점 - 매 TC마다 초기화 필수 - 도착지점에서 뻗어나가는 간선은 존재하면 안된다 - 간선형태로 정보를 저장..
문제 링크: https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" www.acmicpc.net 1. 주의할 점 - -10~10까지 무작정 대입한 후, 비교하지 않도록 한다 -> TLE - 입력을 배열형태로 받아서 해결하기 ..
문제 링크: https://www.acmicpc.net/problem/1400 1400번: 화물차 문제 화물차가 출발지 창고에서 짐을 싣고 배송지 창고까지 짐을 운반하려고 한다. 이 도시의 도로망을 나타낸 지도의 예는 다음과 같다. #A##0##1# .#..#..#. .#..#..#. .###2#.B. 도로망에서 차들은 동, 서, 남, 북의 방향으로만 이동할 수 있고, 지도의 각 문자는 다음과 같은 의미를 가진다. 'A'는 출발지 창고를 나타내고, 지도에서 유일하다. 'B'는 배송지 창고를 나타내고, 지도에서 유일하다. '.'은 차가 들어갈 수 없는 www.acmicpc.net 1. 주의할 점 - 교차로에 들어간 차량은 언제든지 임의의 방향으로 나갈 수 있다. - 교차로의 모양을 초 단위로 바꾼다 - 모..
문제 링크: https://www.acmicpc.net/problem/8452 8452번: 그래프와 쿼리 문제 방향성 있는 그래프 G가 주어진다. 모든 간선의 길이는 1일 때, 당신은 두 가지 쿼리를 처리해야 한다. 간선 하나를 제거한다. 정점 1에서 정점 i 까지의 최단 경로를 출력한다. 경로가 없으면 -1을 출력한다. 입력 첫 번째 줄에 그래프의 정점, 간선의 수와 질의의 수를 나타내는 n, m, q 가 주어진다. (1 ≤ n ≤ 1, 000, 1 ≤ m ≤ 100, 000, 1 ≤ q ≤ 200, 000) 정점들은 순서대로 1부터 n까지 번호가 매겨져 www.acmicpc.net 1. 주의할 점 - 오프라인 쿼리의 원리를 활용한다(간선을 끊는게 아닌 쿼리의 역으로 실행하여 간선을 추가하는 방향으로)..
문제 링크: https://www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다. 이 격자판의 (0, 0) 칸에 한 마리의 뱀이 자리를 잡고 있다. 처음에는 뱀의 크기가 격자 www.acmicpc.net 1. 주의할 점 - 연산이 헷갈리지 않도록 변수를 사용하여 연산값을 저장한다 - 10^8*2 * 10^8*2 만큼의 배열을 생..