문제 https://www.acmicpc.net/problem/23352 23352번: 방탈출 첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다. 둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다. www.acmicpc.net 풀이 BFS + 브루트포스로 해결할 수 있었다. 문제를 해결하기위해 최단거리를 구해야하므로 dist라는 2차원 배열을 만들어주었다 dist를 -1로 초기화 시켜준 이유는 따로 방문 처리 배열을 만들지 않고 dist의 값이 -1일때는 아직 방문을 하지 않은 좌표라는 것을 이용하기 위해서이다. 최대 크기의 비밀번호를 구하기위해서는 모든 좌표(..
문제 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를 돌려주었다. 번호를 매겼으면 이제 다리를 만들어..
