문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS로 해결할 수 있었다. 이 문제 같은 경우 단순 동, 서, 남, 북만 탐색하는 것이 아니라 빌딩의 높이에 따른 동, 서, 남, 북, 상, 하까지 탐색해야하기 때문에 dx, dy, dz라는 3개의 배열을 만들어주었다. 이외에도 우리가 탐색해야할 건물이나 거리 배열 등도 3차원으로 만들어주기만 하면 일반적인 BFS 문제들과 크게 다른 것은 없다. Queue에는 x, y, z 좌표인 3개의 ..
문제 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 처음에 DP 테이블을 P(i)를 활용해서 초기화 해주었다. 이후 점화식을 세워주었다. 최솟값(dp[i]) = 비용의 최솟값을 구해야하므로 기존에 i장을 구매하기위해 필요한 비용(dp[i])과 i - j장을 구매하기위해 필요한 비용 + j장을 구매하기위해 필요한 비용(dp[i - j] + arr[j]) 중 최솟값이라는 점화식을 도출해낼 수 있었고 이를통해 문제를 해결할 수 있었다. 코드 #i..
문제 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 백트래킹으로 문제에 대한 조합을 구해주면 되는데 (문제가 2개일때 ~ 모든 문제를 전부 사용했을때)에 대한 모든 상황에 대해 조합을 돌려주어야 모든 경우의 수를 확인할 수 있다. 조합을 돌리다 조합이 완성되면 check함수를 통해 그 조합이 문제의 조건에 성립하는지 확인해주었고 성립한다면 경우의 수를 증가시켜주었다. 코드 #include #include #include #include using namespace std; int n, l, r, x; int result = 0; vector leve..
문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 골드3 BFS 문제이다. 많은 BFS문제를 풀어봤지만 이 문제를 통해 시행착오를 겪으며 BFS 작동방식에 대해 확실하게 알아야겠다고 느꼈다. 풀이 같은 섬 -> 같은 섬으로의 다리가 만들어 질 수 있기 때문에 보드에 입력을 받을때 육지에 대해서는 1을 -1로 치환하여 받아준다. 이후 setNumber를 통해 같은 섬마다 같은 번호를 붙이도록 BFS를 돌려주었다. 번호를 매겼으면 이제 다리를 만들어..
