난이도 : 골드 4 걸린 시간 : 오래 걸림 문제 벽 부수고 이동하기 문제 보러가기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 풀이 모든 경로를 살펴볼 필요없..

난이도 : 골드 4 걸린 시간 : ㅎㅎ.. 오래 걸림 문제 아기 상어 문제 바로가기 풀이 bfs를 이용하여 먹을 수 있는 고기 찾기 + 상어로부터의 거리 찾기 거리가 가장 가까운 먹을 수 있는 고기들 찾기 그 중 가장 왼쪽 위에 있는 고기 찾기 상어가 해당 물고기의 위치로 이동해서 먹고, 먹은 물고기 개수가 size와 같아지면 size 키우기 상어보다 작은 물고기가 없을 때까지 반복 코드 #include #include #include using namespace std; struct shark { int r; int c; int size = 2; }; struct fish { int r; int c; int distance = 0; fish(int rp, int cp, int dist) { r = rp..

난이도 : 골드 5 걸린 시간 : 25분 문제 적록색약 문제 바로가기 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑..

난이도 : 골드 5 걸린 시간 : 1시간 문제 연구소 문제 바로가기 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연..

난이도 : 골드 3 걸린 시간 : 45분 문제 파티 문제 바로가기 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라. 풀이 모든 점에서 X까지의 시간과 X에서 모든 점까지..

난이도 : 골드 4 걸린 시간 : 1시간 반 이상 문제 문제 바로가기 풀이 우선 완전탐색으로 해당 문제를 생각해본다. 완전탐색으로 구현한다면 dfs를 사용해서 재귀로 구현할 것이다. 재귀의 매개변수(받는 정보)는 현재 위치일 것이고, 내보내는 정보는 현재 위치에서 마지막까지의 경로의 수일 것이다. (0,0)을 처음으로 재귀함수에 넘기면 (0,0)에서 끝까지의 경로의 수이므로 우리가 원하는 답이 나온다. 재귀는 위, 오른쪽, 아래, 왼쪽으로 접한 부분으로 옮겨가며 해당 장소의 경로의 수를 현재 장소의 경로의 수에 더하는 방식으로 진행된다. 이 때, 장소는 맵 안에 있어야한다. 이 때, 내리막길로만 갈 수 있으므로 현재보다 더 높은 수를 가진 장소는 제외이다. 이렇게 구성하면 갔던 곳을 또 가는 경우가 생기..

난이도 : 골드 5 걸린 시간 : 1시간 반 이상 문제 문제 바로가기 오답 처음에 완전탐색으로 하되 최대한 조합의 범위를 줄여서 구현해보았다. 하지만, 시간 초과로 실패..! #include #include #include #include using namespace std; // 6시 4분 시작 => 6시 42분 중단, 11시 12분 시작 => // N > K; for (int i = 0; i > w >> v; vec.push_back(make_pair(w, v)); } // 무게 순 정렬 sort(vec.begin(), vec.end(), compare); // 무게는 같은데 가치가 작은 것은 없애기 for (int i = 1; i < vec.size(..

난이도 : 골드 3 걸린 시간 : 50분 문제 문제 바로가기 풀이 처음에 풀이를 이상하게 생각해서 O(n^3)의 완전탐색 혹은 DP를 사용하는 법을 생각하고 있었다. 그러다가 생각을 다시 해보니 쉽게 풀 수 있는 방법이 있어 20분만에 풀게 되었다. 역시 처음에 풀이를 주석으로 쭉 적어본 후 예제를 테스트 해보고 수행하는 것이 제일 정확하고 알맞은 방법인 듯 하다. 입력의 범위는 10^3로 그다지 높은 편은 아니었지만, 완전탐색 시 O(n^3)이 걸리므로 충분히 시간초과가 나올 수 있는 범위였다. 또한 각 숫자의 범위도 최대 10^3이므로 숫자를 하나씩 내려가며 / 올려가며 푸는 완전탐색 또한 불가능했다. 예제의 힌트를 보니 연속적이지 않은 수열의 흐름도 가능했고, 그렇다면 각 숫자가 보유하고 있는 ma..