-
[BOJ] 15670 : 도로 공사
15670 : 도로 공사 풀이 구현이 좀 귀찮은데 잘 따져서 슥슥 짜주면 된다. 코드 #include <cstdio> int n, m, i, x, y, a[100002]; int inc[100002], dec[100002]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) scanf("%d", &a[i]); inc[1] = dec[1] = 1; for (i = 2; i <= n; i++) inc[i] = inc[i - 1] + (a[i - 1] >= a[i]); for (i = 2; i <= n; i++)...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 잘 짜주자. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return !printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now == del) { cnt--; break; }...
-
[BOJ] 15668 : 방 번호
15668 : 방 번호 풀이 적당히 큰 수까지 어떻게 잘 돌려주면 된다. 코드 #include <cstdio> #include <cstring> #include <algorithm> int n, ans, cnt[10]; int main() { scanf("%d", &n); for (int i = 1; i < std::min(n, 98765); i++) { memset(cnt, 0, sizeof(cnt)); int a = i, b = n - i, flag = 1; while (a) cnt[a % 10]++, a /= 10; while (b) cnt[b % 10]++, b /= 10; for (int j = 0;...
-
[BOJ] 15667 : 2018 연세대학교 프로그래밍 경진대회
15667 : 2018 연세대학교 프로그래밍 경진대회 풀이 폭죽이 폭발하는 경우를 수식으로 잘 나타내서 정리해보자. n = x^2 + x + 1 = x(x+1) + 1 n - 1 = x * (x + 1) 이제 리니어하게 탐색해주자. 코드 #include <cstdio> int main() { int n; scanf("%d", &n); n--; for (int i = 1; i <= n; i++) { if (i * (i + 1) == n) { printf("%d", i); return 0; } } return 0;...
-
[BOJ] 10547 : STUDENTSKO
COCI 2014/2015 Contest #2 3번 10547 : STUDENTSKO 풀이 한 팀에 들어가야 하는 학생들에게 같은 그룹 넘버를 부여하자 그냥 부여하는 건 아니고 먼저 뽑혀야하는 팀부터 오름차순으로 부여하자 그리고 가장 긴 단조증가하는 수열의 길이를 구하자. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, k, len, a[5005], lis[5005]; pair<int, int> p[5005]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]), p[i].first = a[i]; sort(a, a +...
-
[BOJ] 10546 : 배부른 마라토너
COCI 2014/2015 Contest #2 2번 10546 : 배부른 마라토너 10546 : UTRKA 풀이 map 써도 되고 이렇게 짜도 된다 코드 #include <cstdio> int n, i; char a[22], s[22]; int main() { scanf("%d", &n); n *= 2; for (n--; n--;) { scanf("%s", s); for (i = 0; s[i]; i++) a[i] ^= s[i]; } printf("%s", a); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 10545 : 뚜기뚜기메뚜기
COCI 2014/2015 Contest #2 1번 10545 : 뚜기뚜기메뚜기 10545 : MOBITEL 풀이 으쌰으쌰 잘 짜보자. 코드 #include <cstdio> int m[11], t[33] = { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9 }; char s[111]; int main() { for (int i = 1, a; i <= 9; i++) scanf("%d", &a), m[a] = i; scanf("%s", s + 1); for (int i = 1, now, prv = -1; s[i]; i++) { now = t[s[i] - 'a']; if (prv == now) printf("#"); for (int j =...
-
[BOJ] 15562 : 네트워크
15562 : 네트워크 풀이 모든 정점에 대한 sum(max(outdegree - indegree, 0))이 답이다. for (i = 1 ~ n) ans += max(out[i] - in[i], 0); for (i = 1 ~ n) ans += d[i]; ans /= 2; for (i = 1 ~ n) ans += max(d[i], 0); 등등 degree를 관리하는 방식에 따라 같은 식을 여러가지로 변형할 수 있겠다. 어떤 정점의 outdegree가 indegree보다 크다는 것은 해당 정점을 하나보다 많은 네트워크로 분리해서 나누어서 다음 노드로 나아가야 함을 의미한다....
-
[BOJ] 15561 : 구간 합 최대? 2
15561 : 구간 합 최대? 2 풀이 max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i)) = max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V 모든 A[i]를 U * A[i] + V로 바꿔주면 max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다. 15560번에 비해 범위가 크므로 세그먼트 트리 등등을 이용해주자. 코드 #include <cstdio> #include <algorithm>...
-
[BOJ] 15560 : 구간 합 최대? 1
15560 : 구간 합 최대? 1 풀이 max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i)) = max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V 모든 A[i]를 U * A[i] + V로 바꿔주면 max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다. 15561번 풀이에 세그트리를 이용한 구현이 있다. 여긴 나이브한 구현. 코드 #include <cstdio> int...