난이도 : 골드 3 걸린 시간 : 30분 문제 다리 만들기 문제 바로가기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리 모든 섬 사이의 최단 거리를 구해야 함 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산 가중치 없으므로 bfs 이용 각 섬에 속하는 점들은 bfs로 따로 찾기 코드 #include #include using namespace std; int map[101][101]; int direction[4][2] = { ..

난이도 : 골드 4 걸린 시간 : 40분 문제 알파벳 문제 바로가기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 49866 15734 9600 29.155% 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 풀..

난이도 : 골드 5 걸린 시간 : 30분 문제 최소비용 구하기 문제 바로가기 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 최소비용 문제 => bfs / 그래프 탐색(다익스트라) // N 10^3이하 M 10^6 이하 // 출발, 도착, 비용 // 비용 10^6 이하 // 마지막 (출발..

난이도 : 골드 5 걸린 시간 : 1시간 20분 문제 가장 큰 정사각형 문제 바로가기 n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오. 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다. 풀이 작은 문제 : 현재 위치에서 오른쪽과 아래 방향으로 가질 수 있는 정사각형의 최대 크기 재귀식 해당 위치에서 나타날 수 있는 최대 크기 정사각형의 한 변을 Area(row, col)이라고 한다면 Area(row, col) = min(Area(row+1,col)+1, Area(row,col+1)+1, Area(row+1,col+1)+1) 조건 벽에 붙어있으면 Area가 1 값이 ..

난이도 : 골드 3 걸린 시간 : 20분 문제 욕심쟁이 판다 문제 바로가기 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 ..

난이도 : 골드 5 걸린 시간 : 1시간 반 이상 (오류 찾기) 문제 최단경로 문제 바로가기 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 입력 // v, e는 10^5, 10^6이하 int V; int E; cin >> V >> E; int start; // 시작 정점 cin >> start; vector edge(V+1, vector(0)); for (int i = 0; i > from >> to >> val; edge[from].push_back(make_pair(to..

난이도 : 골드 3 걸린 시간 : 1시간 반 이상 문제 합분해 문제 바로가기 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 ..

난이도 : 골드 5 걸린 시간 : 50분 문제 합분해 문제 바로가기 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 작은 문제 : 현재 남은 N에서 남은 K개로 N을 만들 수 있는 경우의 수 재귀 함수 : (N, K) => int 의 형태 사용하는 수 i를 for문 돌면서, j를 1씩 감소시켜서 재귀 종료 조건 N이 0일 때는 남은 수가 모두 0인 경우 1가지만 존재 K가 0이고 N가 0이 아닐 때 남은 경우..