반갑습니다!

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 보고 BFS라고 생각하기 쉽지만, 백트래킹을 통한 완전탐색 문제이다. 이 문제는 크게 2가지 부분으로 구성된다. i번째 사람이 어느 계단으로 갈지 결정하는 부분 구현 계단을 모두 빠져나가는 부분 구현 1번의 경우 백트래킹을 통해 어렵지 않게 모든 경우를 구할 수 있다. 그렇다면 이제는 2번을 구현해야한다. 어느 계단으로 갈 지 결정했다면, 1번 계단으로 가는 사람들이 계단까지 걸리는 시간과 2번 계단으로 가는 사람들이 계단까지 걸리는 시간을 구할 수 있다. 이를 계산한 뒤, 걸리는 시간을 오름차순으로 정렬한다. 그리고 계단을 queue로 구현하여 계단..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 사다리 구현만 잘 하면 쉽게 해결할 수 있다. 코드 #include #include using namespace std; int radder[100][100]; vector start; bool can_finish(int pos) { int y = 0; int x = pos; // 맨 사다리 맨 아래까지 이동 while (y < 99) { // 오른쪽으로 이동이 불가능할 때까지 이동 if (x < 99 && radder[y][x + 1] == 1) while (x < 99 && radder[y][x + 1] == 1) x++; // 왼쪽으로 이동이 불가능할 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 상당히 어려운 문제이다. 아이디어를 생각하는게 어려웠다... 풀이 방은 기본적으로 홀수 방은 위쪽에, 짝수 방은 아래쪽에 배치되어있다. 같은 열에 있는 두 방은 동일 선상으로이라고 볼 수 있으므로 400개의 방을 200개의 방으로 줄여서 생각할 수 있다. 예를 들어, 1번 방에 있던 학생은 4번 방으로, 5번 방에 있던 학생은 6번 방으로 이동해야하는 상황이라고 해보자. 8개였던 방을 4개의 방으로 줄여서 표현해보면 아래의 그림과 같다고 할 수 있다. 그렇다면 이제 배열을 만들어 각 학생들을 옮겨보자. for (int j = a; j > t; for (int c ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 N이 최대 20이므로 완전탐색으로 해결할 수 있다. 탐색을 하면서 값을 갱신하여 가지치기를 하여 최적화했다. 코드 #include #include using namespace std; int n, b, ans; int h[20]; void dfs(int idx, int sum) { // 탐색 중에 나온 합계가 기존에 구한 값보다 크면 종료 if (sum > ans) return; if (sum >= b) { ans = min(ans, sum); return; } for (int i = idx + 1; i < n; i++) dfs(i, sum + h[i]); ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 백트래킹을 통해서 해결하였다. 모든 점을 다 탐색하어 최장 길이를 구할 수 있다. 코드 #include #include using namespace std; int n, m, ans; bool adj[11][11]; bool visited[11]; void dfs(int idx, int cnt) { ans = ans > cnt ? ans : cnt; visited[idx] = true; for (int i = 1; i > t; for (int c = 1; c > n >> m; memset(adj, false, sizeof(adj)); memset(visite..