https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net int N, M; int check[100]; int seq[100]; void backtracking(int cur){ //base condition if(cur == M) { for(int i=0; i

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀가 3번 반복되므로 시간복잡도가 O(n의 log2 3승)이다. 잘못하면 시간초과가 날 수 있으므로 연산량을 최대한 줄이는 것이 좋다. #include using namespace std; int map[6143][3702]; void fractal(int size, int x, int y) { if (size == 1) return; if (size == 3) { for (int i = 0; i < 3; i++) { for (int j = 0; ..

#define SIZE 2187 #include using namespace std; int map[SIZE][SIZE]; void fractal(int size, int x, int y) { if (size == 1) return; if (size == 3) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i != 1 || j != 1) map[x + j][y + i] = 1; } } } size /= 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == 1 && j == 1) continue; else fractal(size, x + size * j, y +..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #define F first #define S second #include #include using namespace std; stack sta; int main(void) { cin.tie(0); ios_base::sync_with_stdio(NULL); long long int max, s, h; int n; while (1) { ci..

1. 문제 https://www.acmicpc.net/problem/14601 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net #include using namespace std; int num; int map[128][128]; bool check(int x1, int y1, int x2, int y2) { for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { if (map[i - 1][j - 1..

//white: 0, black: 1 #define SIZE 64 #include #include #include using namespace std; char col; char map[SIZE][SIZE]; // change - true, not change - false bool check(int x1, int y1, int x2, int y2) { col = map[x1][y1]; for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { if (col != map[i][j]) return true; } } return false; } void dc(int size, int x, int y) { if (size == 1) { cout str; ..

1. 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 풀이 단순히 모든 칸을 한칸씩 다 탐색했더니 시간초과가 나왔다. N의 최대값을 살펴보니 15이다. 최대 size는 2의 15승이므로 32,768이 된다. 즉, 최대넓이는 32,768 x 32,768 = 1,073,741.824로 10억이 넘어간다. 결국 10억이 넘는 칸을 모두 탐색할 경우 대충 10초가 나온다.(1억번 탐색하면 약 1초가 나오므로) 따라서 구역을 확인 후..

1. 문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택을 활용한 전형적인 괄호의 유효성을 검사하는 문제이다. 2. 풀이 문자열을 탐색하면서 stack이 비어있으면 추가한다. stack이 차있는 경우 stack.top와 문자를 비교하여 짝이 맞으면 stack.top을 제거하고 짝이 맞지 않으면 현재 문자를 stack에 추가한다. 3. 코드 #include #include #include using names..