문제 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친� www.acmicpc.net 문제 풀이 문제에서는 N명의 사람이 있고, 세 사람을 선택할 때 세 사람이 모두 친구이고 세 사람의 친구 수의 합이 최소가 되는 경우를 찾아 반환하여야 한다. 문제의 조건에는 세 사람을 선택할 경우 세 사람은 친구에서 제외해야 한다는 조건이 있다. 처음에는 문제를 `DFS`를 통해 접근해야 하지 않나 라고 생각하였는데 세 사람을 선택하는 것을 `3중 반복문`을 통해 경우를 탐색하면 시간 초과가 발생하지 않고 문제를..
문제 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net 문제 풀이 A, B의 숫자가 주어질 때 A의 자릿수로 구할 수 있는 순열을 구하여 B보다 작으면서 가장 큰 값을 반환하는 문제이다. `DFS`를 통해 순열을 구하면서, B보다 작은지 확인하고 최대 값을 갱신해 주면 된다. 중간에 가지치기를 해주고 싶어서, 순열의 처음 값이 B의 첫 번째 값보다 크다면 가지를 뻗지 않게 하려고 했는데... 74~75% 정도에서 `틀렸습니다.` 를 출력한다. 가지치지를 하지 않으니 정답을 맞출 수 있었다. 코..
문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우를 구하는 문제이다. 문제를 풀기 위해 경우를 찾아보면 다음과 같은 규칙을 찾을 수 있다. N이 홀수인 경우 경우의 수는 0이다. 2x1, 1x2로는 N이 홀수인 경우 채울 수 없다. N = 2 3가지 경우의 수 N = 4 2의 경우의 수 * 3 + 2 N = 6 4의 경우의 수 * 3 + 2의 경우의 수 * 2 + 2 N = 8 6의 경우의 수 * 3 + 4의 경우의 수 * 2 + 2의 경우의 수 * 2 + 2 `dp[N] = dp[N - 2] * 3 + dp[N - 4] * 2 + ... dp..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 주어진 입력 값 N, M에 따라 간선 정보를 토대로 그래프를 초기화 해준 후 각 노드마다 연결된 노드들로 경로를 탐색하면 된다. 이때 백트랙킹이 필요하므로 `DFS`로 탐색을 진행하여 연결된 노드의 개수가 크면 갱신시켜주면 문제를 해결할 수 있다. 코드 from collections import defaultdict T = int(input()) def dfs(cur_node, cnt): global answer if answer < cnt: answer = cnt for next_node in graph[cur_node]: if not visit..
