-
[BOJ] 1509 : 팰린드롬 분할
1509 : 팰린드롬 분할 풀이 나중에 써야징 코드 #include <stdio.h> #include <string.h> const int n_ = 2500 + 5; int len, dp[n_][n_], res[n_]; char data[n_]; int main() { scanf("%s", data); len = strlen(data); for (int i = 1; i <= len; i++) dp[i][i] = 1; for (int i = 1; i <= len - 1; i++) if (data[i - 1] == data[i]) dp[i][i + 1] = 1; for (int i = 2; i <= len...
-
[BOJ] 10828 : 스택
10828 : 스택 풀이 스택을 쓰자. 코드 #include <bits/stdc++.h> using namespace std; int n, a; stack<int> sta; string str; int main() { for (scanf("%d", &n); n; n--) { cin >> str; if (str == "push") { scanf("%d", &a); sta.push(a); } else if (str == "pop") { if (sta.empty()) printf("-1\n"); else printf("%d\n", sta.top()), sta.pop(); } else if (str == "size") { printf("%d\n", sta.size()); } else if (str == "empty") { printf("%d\n", sta.empty()); } else { if...
-
[BOJ] 13308 : 주유소
13308 : 주유소 풀이 2016 koi 전국대회 2번 문제이다. 뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다. 음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다! 여기서 트릭(?)을 한 번 써보자. priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면 이미 지금보다 작은 값으로 방문했었음이 보장된다. 그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef...
-
[BOJ] 11866 : 조세퍼스 문제 0
11866 : 조세퍼스 문제 0 풀이 단순 구현 코드 #include <bits/stdc++.h> using namespace std; int n, m, pos; vector<int> a; int main() { cin >> n >> m; for (int i = 0; i < n; i++) a.push_back(i + 1); printf("<"); while (1) { pos = (pos + m - 1) % a.size(); if (a.size() > 1) { printf("%d, ", a[pos]); } else { printf("%d>", a[pos]); break; } a.erase(a.begin() + pos); } return 0; }...
-
[BOJ] 4963 : 섬의 개수
4963 : 섬의 개수 풀이 dfs를 돌리자 코드 #include <stdio.h> const int dx[] = { 0,0,1,-1,1,1,-1,-1 }; const int dy[] = { -1,1,0,0,1,-1,-1,1 }; int n, m; int a[51][51]; void dfs(int x, int y) { a[x][y] = 0; for (int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m)...
-
[BOJ] 10799 : 쇠막대기
10799 : 쇠막대기 풀이 괄호가 나오는 문제는 대부분 stack을 이용하면 풀린다! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; int cnt, ans; string str; int cmp(char a, char b) { a -= '(', b -= '('; if (a == 0 && b == 0) return 1; if (a == 0 && b == 1) return 2; if (a == 1 && b == 0) return 3; if (a == 1 && b == 1) return 4;...
-
[BOJ] 10801 : 카드게임
10801 : 카드게임 풀이 단순 구현. 코드 #include <bits/stdc++.h> using namespace std; int a[20], x, y; int main() { for (int i = 0; i < 20; i++) scanf("%d", &a[i]); for (int i = 0; i < 10; i++) { if (a[i] > a[i + 10]) x++; if (a[i] < a[i + 10]) y++; } if (x > y) puts("A"); else if (x < y) puts("B"); else puts("D"); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 12911 : 좋아하는 배열
12911 : 좋아하는 배열 풀이 dp[i][j] = 길이가 i이고, 첫번째 숫자가 j 나머지 연산에 주의하자. 코드 #include <stdio.h> typedef long long ll; const int mod = 1000000007; int N, K; int dp[11][100001]; ll sum[11]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i <= K; ++i) dp[1][i] = 1; sum[1] = K; for (int i = 2; i <= N; ++i) { sum[i - 1] += mod; for (int j =...
-
[BOJ] 12869 : 뮤탈리스크
12869 : 뮤탈리스크 풀이 음 원래 dp로 풀려고 했는데 그냥 bfs로 풀었다. dp[i][j][k] = 1번, 2번, 3번 scv의 체력으로 두고 풀어도 된다. 코드 #include <bits/stdc++.h> using namespace std; int N, A[3], ans = 987654321; const int D[6][3] = { {1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1} }; bool chk[61][61][61][20]; struct ABC { int a, b, c, x; ABC() {} ABC(int a, int b, int c, int x) : a(a), b(b), c(c), x(x) {} }; int main() { scanf("%d", &N); for (int...
-
[BOJ] 2661 : 좋은 수열
2661 : 좋은 수열 풀이 재귀로 작은 숫자부터 들어가면서 문자를 비교해주자 코드 #include <bits/stdc++.h> using namespace std; int n, a[88]; void gogo(int cnt) { for (int i = 1; i <= cnt / 2; i++) { if (equal(a + cnt - i, a + cnt, a + cnt - i - i)) return; } if (cnt == n) { for (int i = 0; i < n; i++) printf("%d", a[i]); exit(0); } for (int i...