본문 바로가기
728x90
반응형

Algorithm/C++

 (111)
[C++] 2960 : 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net #include #include using namespace std; bool arr[1001]; int n, k, cnt = 0; void primeNumberSieve() { for (int i = 2; i k; //입력 primeNumberSieve(); //에라토스테네스의 체 실행 return 0; } 문제의 알고리즘 그대로 구현하면 해결 할 수 있습니다.
[C++] 14852 : 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; int arr[1000001] = { 1,2,7 }; int f(int n) { if (arr[n] != 0) return arr[n]; int result = 3 * f(n - 2) + 2 * f(n - 1); for (int i = 3; i > n; cout
[C++] 2133 : 타일 채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net #include using namespace std; int n; int arr[31] = {1,0,3}; int f(int n) { //점화식 : f(n) = 3*f(n-2) + 2*f(n-4) + 2*f(n-6) + ... +2*f(0) if (n % 2) return 0; //홀수면 0 리턴 if (arr[n] != 0) return arr[n]; //짝수일 때 0이 아닌 값이면 그 배열값 리턴 int result = 3 * f(n - 2); //점화식 구할 때, 앞에 3*f(n-2) 부분 for (i..
[C++] 11727 : 2 X n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net #include using namespace std; int n; int arr[1001] = { 0,1,3 }; int f(int n) { //동적 계획법으로 구현 if (arr[n] != 0) return arr[n]; return arr[n] = (f(n - 1) + 2 * f(n - 2)) % 10007; } int main(void) { cin >> n; cout
[C++] 11726 : 2 X n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #include using namespace std; int n; int arr[1001] = { 0,1,2 }; int f(int n) { //동적 계획법으로 구현 if (arr[n] != 0) return arr[n]; return arr[n] = (f(n - 1) + f(n - 2)) % 10007; } int main(void) { cin >> n; cout
[C++] 9184 : 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net #include using namespace std; int abc[21][21][21]; //저장할 값 int w(int a, int b, int c) { //조건에 따라 설정 if (a 20) return w(20, 20, 20); //값을 abc[a][b][c]에 넣어주면서 중복계산 줄이기 else if (abc[a][b][c] != 0) return abc[a][b][c]; else if (a..
[C++] 1197 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net #include #include #include using namespace std; int V, E; //(정점 개수),(간선 개수) int node_info[10001]; //정점들간의 연결 정보(일부만 이용) class Edge { //간선 정보(간선과 연결된 두 정점, 비용, 정렬 기준 등) public: int node[2], cost; //..
[C++] 1922 : 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net #include #include #include using namespace std; int n, m; //(정점 수),(간선 수) class Edge { //간선과 연결된 정점 2개와 비용 등의 정보 public: int node[2]; //연결된 정점 int cost; //비용 Edge(int a, int b, int c) { //초기화 this->node[0] = a; this->node[1] = b; this->cost = c; } bool operator cost n >> m;..
728x90
반응형

티스토리툴바