결국 오고야 마는 것들

dp문제긴 한데... 이런 규칙 찾기 문제는 풀어도 영 뿌듯하지가 않다... 최댓값은 홀수인 경우 7 이후에 2마다 1을 추가하고, 짝수인 경우엔 그냥 2마다 1을 추가하면 된다. 최솟값은 숫자별 최소값을 쭉 적어보면 17까지는 예외가 있는데, 18 이후부터는 7 마다 이전 숫자에 8을 더해 만드는 규칙을 찾을 수 있다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[22] = { 0, 0, 1, 7, 4, 2, 6, 8, 10, 18, 22, 20, 28, 68, 88, 108, 188, 200, 208, 288, 688, 888 }; int t; void input() { fastio; c..

혼내주기 2021. 8. 1. 22:56

투 포인터로 구간에서 중복되는 숫자가 k개를 넘어가면 중복된 숫자가 구간에서 제외될 때 까지 왼쪽 포인터를 밀어주면 된다. 지금까지 한칸씩만 밀다가 조건을 만족할 때 까지 포인터를 움직이는 문제는 처음 만나서 좀 헤맸다. 유연한 사고 능력이 부족하다! #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[200000], cnt[100001]; int n, k; void input() { fastio; cin >> n >> k; for(int i = 0; i > arr[i]; } int main() { input(); int ans = 0; for(int e = 0, s = ..

혼내주기 2021. 8. 1. 22:55

처음에 bfs로 방문한 곳을 다시 방문할 수 있으면 -1을 출력하도록 구현했는데 틀렸다. 아무리 생각해도 틀릴 이유가 없는데 틀려서 질문글에서 반례를 찾고 dfs + dp로 바꿔서 풀었다. 반례는 스포 방지를 위해 맨 아래에 적어두었다. 이 문제 또한 실제 코딩테스트 문제였으면 반례를 떠올리지 못했을 것 같다... 경우의 수를 좀 더 엄밀하게 생각하는 능력을 기르고 싶다... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; bool visited[50][50]; int board[50][50], cache[50][..

혼내주기 2021. 8. 1. 22:55

비트마스크 dp인줄 알았는데 그냥 완전탐색으로 풀 수 있는 문제였다... 이번 문제도 corner case를 잡지 못해서 오래 헤맸다... 멘탈 바사삭... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string words[50]; bool check[26]; char must[5] = {'a', 'n', 't', 'c', 'i'}; int n, k, tot = 0, ans = 0; void input() { fastio; for(int i = 0; i > n >> k; for(int i = 0; i < n; ++i) { ci..

혼내주기 2021. 8. 1. 22:54

지이이이ㅣ이인짜 많이 헤맸는데, 결과적으론 처음 짠 코드에서 index 처리를 잘 못해서 지구 한바퀴 돈 셈이다. 우울하다 진짜... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; string arr[10]; bool check[26]; char alphabet[10]; int match[26]; int n, ans = 0, tot = 0; void input() { fastio; cin >> n; for(int i = 0; i > arr[i]; for(int j = 0; j < arr[i].size(); ++j) { if(check[arr[i][j] - 'A']) contin..

혼내주기 2021. 8. 1. 22:53

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[4000][4]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i][j]; } int main() { input(); vector v; v.reserve(n*n); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { v.push_back(arr[i][2] + arr[j][3]); } } sort(v.begin(), v.end()); long long ans..

혼내주기 2021. 8. 1. 22:52

각 배열의 최대 크기가 1000이기 때문에 배열의 모든 부분합의 갯수는 500500이 최대가 된다. 두 배열의 모든 부분합을 정렬하고 이분탐색으로 T를 만족하는 조합의 갯수를 세면 된다. T와 모든 배열의 값이 0이면 답이 int범위를 벗어나기 때문에 long long으로 선언해야한다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int A[1001], B[1001]; int T, n, m; void input() { fastio; cin >> T >> n; for(int i = 1; i > A[i]; A[i] += A[i-1]; } cin >> m; for(int i = 1; i > B[i]; B[i] ..

혼내주기 2021. 8. 1. 22:51

한번에 최대 몇개의 회의가 중복되서 진행되는지를 구하면 된다. 회의 시작 시간을 오름차순으로 정렬한 뒤, 매 회의마다 cnt를 증가시키고(새로운 회의) 우큐에 종료시간을 넣는다. 이후 현재 진행중인 회의의 시작 이전에 끝나는 회의를 우큐에서 모두 꺼내고 cnt를 감소시킨다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; pair meetings[100000]; int n; void input() { fastio; cin >> n; for(int i = 0; i > meetings[i].first >> meetings[i].second; } int main() { input(); s..

혼내주기 2021. 8. 1. 22:50