-
[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...
-
[BOJ] 3108 : 로고
3108 : 로고 풀이 사각형을 하나의 노드로 보자. 어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자. 연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다. 연필은 연결 요소의 개수 - 1번 들어주면 된다. 단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자. (x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다. Flood fill로 풀어도 된다. 코드 #include <cstdio> #include <algorithm> #define y1 fu using namespace std; const int n_ = 1000 +...