이 험난한 세상에서어어~

문제 설명 민오는 1번부터 N번까지 문제를 푼다고 한다. 이때 난이도는 1번부터 N번까지 점차 올라간다. 민오가 문제를 풀 때는 몇 가지 조건이 있다. 1. N개의 문제는 모두 풀어야 한다. 2. 어느 한 문제에 먼저 풀어야 좋은 문제가 존재한다면 먼저 풀어야하는 문제들을 모두 풀어야 현재 문제를 풀 수 있다. 3. 문제들은 난이도가 쉬운 순으로 풀어야 한다. 이때 위의 조건들을 지키면서 민오가 문제를 푸는 순서를 구하라. https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A..

문제 설명 치즈(2636) 문제에서 공기와 면을 두 개 이상 맞닿고 있는 치즈만 녹이는 것이다. https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 문제 풀이 해당 문제의 풀이를 보기에 앞에 골드 4 레벨의 치즈 문제(백준, 2636)를 한 번 풀고 오는 것을 추천한다. https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치..

문제 풀이 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 1부터 N까지 노드가 있을 때 해당 숫자와 연결된 배열이 주어진다. 여기서 순열 사이클의 수를 찾는 문제이다. 문제 풀이 첫 번째 풀이 처음에는 간단하게 반복문으로 풀어줬다. 시작하는 노드 start와 그래프를 탐색하면서 변하는 현재 노드 current, 그리고 현재 노드와 연결된 다음 노드 next를 이용했다. ..

문제 설명 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다. 도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다. 강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다. 예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5,..

문제 설명 nxn 모양의 바둑판이 있다. 이때 (0, 0)에서부터 (n-1, n-1)까지 가려고 한다. 다만, 검은 방이 존재하여 갈 수 없을지도 모른다. 때문에 (0, 0)에서부터 (n-1, n-1)까지 갈 수 있으면서 검은 방을 최소한 하얀 방으로 만드는 그 수를 구하여라 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 문제 풀이 잘못된 풀이 문제를 본 처음에는 검은 방을 0부터 검은 방의 수 만큼까지 조합으로 만들어서 하얀방을 표시한 다음..

문제 설명 nxm 칸에 구멍이 있는 치즈가 하나 놓여 있다. 공기와 닿은 칸이 1시간 지나면 녹게 되는데, 치즈의 구멍에는 칸이 없지만 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 이때 치즈가 다 녹는 시간과 마지막 시간에 남은 치즈의 수를 구하여라 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 풀이 언뜻 보면 쉬워 보이지만, 문제를 파악할 때 함정이 있는데 바로 탐색의 중심을 치즈가 아닌 공기로 잡아야 한다는 것이다. 나는 처음에 치즈를 ..