문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 M명의 사람이 입국심사를 받으려고 할 때, 입국 심사의 소요 시간이 최소가 되는 시간을 출력하는 문제이다. 문제를 풀기 위해서는 `이분 탐색`을 통해, 심사가 가능한 최소 시간을 구할 수 있다. 이 문제에서 이분 탐색의 `mid` 값은 입국 심사하는데 소요되는 전체 시간을 의미한다. 예를 들어 `mid`가 30초라면 30 // 심사하는데 걸리는 시간을 구하게 되면 입국할 수 있는 사람 수가 결정되게 된다. 코드 T = int(input()) for test_case in range(1, T + 1): answer = 0 n, m = map(int,..
문제 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..
