private static void life()

중량제한 성공 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 128 MB 8711 1856 1182 24.049% 문제 N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, ..

[ 파스칼의 삼각형 ] 파스칼의 삼각형은, 아래와 같이 조합(Combination)과 연관이 있다. 위에서 주어진대로, 로 가정하면 구현하기 매우 간편해진다. 파스칼의 삼각형을 코드로 구현하면 아래와 같다. m과 n을 입력받아서 을 출력한다. #include #define MAX_ARRAY_SIZE (31) int main(void) { int n, m; int D[MAX_ARRAY_SIZE][MAX_ARRAY_SIZE] = { 1, }; scanf("%d %d", &n, &m); for (int i = 1; i

설명설명 [ BFS, DFS 구현(인접리스트 활용) ] DFS와 BFS 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB4284613356802329.497%문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 ..

[ Quick Sort ] - 이미 정렬되어있는 경우 O(N^2) 알고리즘이 됨에 유의#include #include using namespace std; void swap(int input[], int a, int b) { int temp = input[a]; input[a] = input[b]; input[b] = temp; } int partition(int input[], int low, int high) { int index = low; for (int i = low; i < high; i++) // 여기서 high를 일단 pivot으로 보고있으므로 high는 빠져야한다. { if (input[i] = high) return; int pivot = partition(input, low, high..

[ 소수 구하기 ] 1 ~ N까지 모든 소수를 구하기 - 에라토스테네스의 체 1. 1은 소수가 아니다. 2. 2부터 시작하여 아직 지워지지 않은 수는 소수이다. 3. 소수를 찾았으면, 그 수의 배수를 모두 지운다. 4. 루트 N까지만 검사를 해보면 된다. Step 0. 초기상태. 1은 소수가 아니므로 지운다. Step 1. 2부터 시작한다. 2는 지워지지 않았으므로 2는 소수이며 2의 배수를 모두 지운다. Step 2. 그다음 수 3이 지워지지 않았으므로, 3도 소수이고, 3의 배수를 모두 지운다. Step 3. 4는 이미 지워져있으므로, 소수가 아니다. Step 4. 이런식으로 루트N까지 검사했을 때, 남아있는 수들이 모두 소수이다. [ 소수 구하기 문제 ] 문제 링크 : https://www.acmi..

[ 최대공약수 ] - 유클리드 호제법을 이용해서 구할 수 있다.- 두 수 A,B의 최대공약수를 구하려면, A를 B로 나눈 나머지가 r이라고 할 때, GCD(A, B) = GCD(B, r) r = 0이 될 때의 B가 최대 공약수이다. int GCD(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }[ 최소공배수 ] - 다음 관계를 이용하여 푼다. LCM * GCD = A * B LCM = A * B / GCD [ N진법 수를 쉽게 10진법 수로 바꾸기 ] ex) N = 3진법 수 102를 10진법 수로 바꾸기 왼쪽에서부터 순차적으로 전개해나간다. 102 먼저 가장 왼쪽에 있는 수 1 -> 1기존 수에 3을 곱하고 0을 더한..

문제 링크 : https://www.acmicpc.net/problem/2011 암호코드 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB141022492187219.059%문제상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러가지가 있어.상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오..

문제 링크 : https://www.acmicpc.net/problem/2225 합분해 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB71063061228442.684%문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.예제 입력 1 복사20 2 예제 출력 1 복사21 [ 문제 풀이 ] D[K][N] = K개를 더해서 합이 N이 되는 수 [ 최종 구현(C++..

문제 링크 : https://www.acmicpc.net/problem/2133 타일 채우기 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB115654028314235.319%문제3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.입력첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.출력첫째 줄에 경우의 수를 출력한다.예제 입력 1 복사2 예제 출력 1 복사3 힌트아래 그림은 3×12 벽을 타일로 채운 예시이다. [ 문제 풀이 ] D[i]를 3 x i 벽을 타일로 채울 수 있는 경우의 수로 둔다. 경우의 수를 계산해보면, 즉, D[i] = D[i-2] x 3 + D[i- 4] x 2D[i - 6] x 2D[i - 8] x 2...D[0] x 2 ※ 주의. ..

문제 링크 : https://www.acmicpc.net/problem/1699 제곱수의 합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB104194279317241.046%문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할..