총 6문제를 풀면서 5번 틀렸다 ㅠㅠ A번에서도 틀리는 걸 보면 정확성이 너무 떨어진 것 같다. A번: 수에 0.5를 더한 뒤 내림하면 반올림이 되는데, 실수 오차를 막기 위해 0.5001을 더했다. #include #include using namespace std; int main() { double N; cin >> N; cout > N; int i; for (i = 0; i > K; int t = 0; while (K--) { int a; cin >> a; t *= 79; t += a+1; t %= 7979797979797979LL; } x.insert(t); } cout > N; int i; for (i = 0; i < N; i++) { int a,b;..
망했다 ㅠㅠ 4문제밖에 못 풀었다. A번 풀이: 1개, 2개, 3개를 지우는 모든 경우를 생각해주면 풀린다. #include #include #include using namespace std; int isp(int n) { int i; for (i = 2; i > T; while (T--) { int N; cin >> N; vectorx; int i; int su = 0; for (i = 0; i > a; su+=a; x.push_back..
문제 링크:https://oj.uz/problem/view/APIO13_interference 문제 보기 - Interference (APIO13_interference) :: oj.uz Wikipedia에 따르면, '자기상관'이란 신호의 교차상관관계를 말한다. 높은 자기상관값을 가지는 것은 혼선을 증가시키므로 무선 신호에 좋지 않다. 만약 당신이 미래에 신호를 다루는 무선 통신 연 oj.uz 답을 최소화하기 위하서 나는 hill climbing 기법을 사용했다. 이 기법은 현재 상태에서 인접한(원소 차이가 하나인) 해 중 가장 좋은 해를 찾고, 그 해로 이동하는 것을 반복하는 기법이다. 이 기법을 사용해서 변화가 없을 때까지 탐색하고, 랜덤한 해로 이동하는 것을 반복해서 답을 구했다. 코드: #incl..
만약 모든 원의 반지름이 같다면, 격자를 반지름*반지름의 부분 정사각형으로 나눈 뒤, 원의 중심을 중심으로 하는 25개의 부분 정사각형만 봐서 지우면 된다. 모든 원의 크기가 다를 때도 이와 비슷한 전략을 쓸 수 있다. 부분 정사각형의 크기가 현재 탐색하는 원의 반지름 이상이면서 반지름의 2배보다 작도록 하면 탐색하는 범위 밖의 정사각형이 없지도, 부분 정사각형이 너무 커져서 의미가 없어지지도, 부분 정사각형을 그리느냐고 시간을 많이 쓰지도 않게 된다. 시간 복잡도: N*25*unordered_map으로 인한 매우 큰 상수로, 시간이 빡빡한 편이다. #include #include #include #include #define int long long using namespace std; unordere..
관찰 1. 간선으로 이웃한 정점은 허브와의 거리가 최대 1 차이 난다. 관찰 2. 스패닝 트리를 만들면 모든 정점에서 허브 i까지의 거리를 N-1개의 -1에서 1 사이의 정수로 표현할 수 있다. i에서 i까지의 거리는 0이라고 알 수 있고, dfs를 통해 거리를 계산해 줄 수 있기 때문이다. 이를 통하면 최적의 전략은 스패닝 트리와 간선에 대한 정보를 보내주고, 그것을 통해서 계산하는 것임을 알 수 있다. 스패닝 트리는 각 정점의 부모를 저장하면 9990 비트로 보낼 수 있다. 거리는 이론상 999*36*log 3개의 비트로 나타낼 수 있고, 실제로는 5개의 정수를 그룹지은 뒤 이를 8개의 비트로 나타내어 보냈다. 이는 57600비트를 사용하고, 이를 통해 만점을 받을 수 있다. #include "gra..
A번: (S[N-1]=='o'):"Yes":"No", 단순한 구현 문제이다. #include #include #include #include using namespace std; setx; pairarr[200100]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; string s; cin >> s; cout > a; cout > N; int i; for (i = 0; i > arr[i]; } for (i = 0; i > arr2[i]; } for (i = 0; i < 4; i++) { int j,k; for (j = 0; j < N; j++) { f..
내 스택에 관한 글 를 읽거나, 스택에 대한 지식이 있어야 풀이를 이해할 수 있다. 괄호의 값: https://www.acmicpc.net/problem/2504 풀이: 스택을 이용해서 현재 쌍을 만들어야 하는 괄호들을 나온 순서대로 저장해주는 것이 풀이의 핵심이다. 괄호 스택을 비우고 닫힐 때 추가되는 점수를 1로 해 준 뒤, 문자열을 순서대로 보면서 여는 괄호가 들어오면 스택에 넣고, 현재 닫힐 때 추가되는 점수에 괄호의 값을 곱해준다. 닫는 괄호가 들어오면, 괄호가 스택 맨 위의 괄호와 맞는지 확인해 준 후 맞지 않으면 0을 출력해 준 뒤, 스택 맨 위 괄호와 이웃해 있으면 닫힐 때 추가되는 점수를 정답에 더해 준 후, 스택에서 pop을 하고, 닫힐 때 추가되는 점수에 괄호의 값을 나눠주면 된다. ..
개요:스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조이다. 연산: push(x): 스택 가장 위 에 x를 추가한다. pop(): 스택 가장 위에 있는 항목을 제거한다. top(): 가장 위에 있는 항목을 반환한다. size(): 스택의 크기를 반환한다. 구현: 배열이나 링크드 리스트를 이용해 구현할 수 있는데, 나는 배열로 구현했다. #include #include #include //https://www.acmicpc.net/problem/10828 문제 풀이 using namespace std; template class stack { T arr[1000100]; const int maxsiz = 1000000; int siz = 0; publ..