목록분류 전체보기 (370)
cgy12306
dp[4]=11까지는 생각을 했지만 그 이후에 답이 안나와서 다른사람의 블로그를 참고했다. #include using namespace std; int dp[32]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; dp[0] = 1; dp[1] = 0; dp[2] = 3; for (int i = 4; i = 0; j -= 2) { dp[i] += dp[j] * 2; } } cout
// https://www.acmicpc.net/problem/2357 // 최솟값과 최댓값 #include #include using namespace std; int INF = 1000000001; int N, M; int arr[100002]; int max_tree[4 * 100002 + 4]; int min_tree[4 * 100002 + 4]; int init_min(int start, int end, int node) { if (start == end) return min_tree[node] = arr[start]; int mid = (start + end) / 2; return min_tree[node] = min(init_min(start, mid, node * 2), init_min(m..
100000개의 테스트 개수를 주고, 1부터 1,000,000,000까지의 범위를 주어졌을 때 일반적으로 코드를 짜면 시간초과가 발생한다. 세그먼트 트리를 이용해 문제를 해결하면 시간초과를 방지할 수 있음 // https://www.acmicpc.net/problem/10868 // 최솟값 #include #include using namespace std; int arr[100002]; int tree[4 * 100002 + 4]; int INF = 1000000001; int init(int start, int end, int node) { if(start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; return tree[..
// https://www.acmicpc.net/problem/10026 // 적록색약 #include #include using namespace std; int N; char map[101][101]; int visited[101][101]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; void dfs(int x, int y, int cnt) { visited[x][y] = cnt; for (int i = 0; i = N || ny >= N || map[x][y] != map[nx][ny]) continue; if ..
// https://www.acmicpc.net/problem/2589 // 보물섬 #include #include #include #include using namespace std; int N, M; char map[51][51]; int visited[51][51]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, 1, -1 }; int bfs(int x, int y) { memset(visited, 0, sizeof(visited)); queue q; q.push({ x, y }); visited[x][y] = 1; while (!q.empty()) { x = q.front().first; y = q.front().second; q.pop(); for (int ..
// https://www.acmicpc.net/problem/5014 // 스타트링크 #include #include using namespace std; int F, S, G, U, D; int dx[2]; int visited[1000002]; queue q; int bfs(int start) { q.push(start); visited[start] = 1; while (!q.empty()) { int x = q.front(); q.pop(); if (x == G) return visited[x] - 1; for (int i = 0; i F) continue; if (visited[nx] == 0) { vis..
// https://www.acmicpc.net/problem/1987 // 알파벳 #include #include #include using namespace std; int R, C, ans = 0; char map[22][22]; bool visited[27]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0 , 0, 1, -1 }; void dfs(int x, int y, int cnt) { ans = max(ans, cnt); for (int i = 0; i = R || ny >= C) continue; if (!visited..
// https://www.acmicpc.net/problem/18119 // 단어 암기 #include #include using namespace std; int N, M; int alp = 0; int arr[10001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for (int i = 0; i s; for (int j = 0; j o >> x; alp ^= 1