mojo's Blog

문제 링크 : 1944번: 복제 로봇 (acmicpc.net) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 문제이다. 문제의 input 을 고려해서 어떻게 정답을 찾을지를 생각해보도록 하자. 5 2 11111 1S001 10001 1K1K1 11111 우선, 문제에서 요구한 것은 로봇의 시작지점인 S 부터 열쇠 K 를 모두 획득하는데 움직이는 횟수의 합을 최소로 하는 것이다. (2, 2) 에 있는 S 로 부터 시작하여 (2, 2) => (4, 2) => (4..

문제 링크 : 19236번: 청소년 상어 (acmicpc.net) 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 완전 탐색을 이용한 구현 문제이다. 문제 설명에 앞서 클래스 및 선언한 배열 및 상수에 대한 설명을 하려고 한다. ※ class Fish Fish 라는 클래스를 선언하였고 아래코드와 같이 구현하였다. class Fish { public: bool live; int x, y, direction; Fish() {} Fish(int x, int y, int direction, bool ..

문제 링크 : 1949번: 우수 마을 (acmicpc.net) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리에서의 다이나믹 프로그래밍 문제이다. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마..

문제 링크 : 9879번: Cross Country Skiing (acmicpc.net) 9879번: Cross Country Skiing The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 C; for (int i = 1; i elev[i][j]; for (int i = 1; i point[++cnt]; if (point[cnt]) P++; } } } int get_vertex(int x, int y) { return ((x - 1) * C + y); } bool compare(pair x, pair y) { return (x.first < y.first); } void..

문제 링크 : 17136번: 색종이 붙이기 (acmicpc.net) 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙..

문제 링크 : 9370번: 미확인 도착지 (acmicpc.net) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요..