늘

오랜만에 백준 문제 글을 작성하는 것 같다.😳 회문.. 오래 걸렸다. 처음 문제를 푸는데 안 풀려서 잠시 미뤄두고 다시 머리를 식히고 푸니 그제야 해결이 되었다. 요즘 구현 문제들을 푸는데 상당히 아이디어를 요구하는 방식과 반례 처리? 가 중요한 것 같다는 생각이 든다. 그리고 컨디션이 중요한 느낌..(희한하게 어쩔 때는 잘 풀리는데 안 풀리는 날에는 하나도 안 풀리는 문제 부류...🤣🤫) 풀이 과정을 소개해보겠다. 처음에는 재귀문을 통해서 해결하려고 했다. 시간 초과 풀이 #include #include using namespace std; string s; int l = 0; int r; int flag = 0; int check(int l, int r) { while (l < r) { if (s[l..

문제부터 보면 전형적인 DP 문제라고 생각이 든다. 하지만 문제에 시간초를 보면 2초나 주어진다. 그래서 이 문제를 DP로 풀어야만 하는가 의문이 들면서 접근을 했다. 우선 문제 풀이 생각으로는 시간 제한도 2초이고 입력 수도 1000인것을 감안해서 넉넉하기 때문에 1일부터 Ti 시간만큼 뛰어가면서 전부 더해보는 방식으로 했다. #include #include #include using namespace std; int n; int visited[1001]; vector works; int answer; int pays; void start(int x, int pre) { if (x == n) { answer = max(answer, pays); return; } if (x > n) { answer = ..

진짜 간단해보였는데, 돌릴때마다 새로운 반례들을 만나면서 생각보다 시간이 오래걸렸다.. 알고리즘은 덱 이라는 자료구조를 이용하여 앞에서와 뒤에서 빼는 방식을 사용해야했다. 그렇지 않고 v.erase(v.begin())으로 앞에서 지우면 시간초과가 나왔다. 그리고reverse할 때, 진짜로 reverse하면 안되고 reverse했을땐 뒤에서, 정방향일 땐, 앞에서 pop해주는 방식으로 해결했다. 주저리 주저리 설명보단 역시 코드로 보는게 빠를듯 하다. 반례를 여러번 고치다보니 조금 지저분하긴 하다.... #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); in..

알고리즘은 간단했다. 단순히 완전 탐색 방식으로 조합의 모든 경우를 계산하고 중복되는 만큼 ex) aabab와 같은 경우 3! 2!으로 나눠주면 됐다. 문자열보단 조합론(?)에 가까운 문제였다. 하지만 조합은 1 3 2 처럼 모두 다른 숫자나 문자로 구성되었지만 이 문제는 중복된 문자들도 있기 때문에 각 문자마다 id값을 주어 구분하였다. #include #include #include using namespace std; vector v;// id, 문자 int over[27]; int visited[27]; string s; int n; char ans[11]; int res = 0; int factorial(int n) { long long sum = 1; for (int i = 1; i > s; ..

UCPC 2020 예선 G번 문제이다! UCPC 2020 예선 www.acmicpc.net 문제는 위와 같다. 생각보다 단순한 BFS를 돌리면 됐었다. 하지만 날짜를 증가시켜줄 때, 한꺼번에 넣어줘야하기 떄문에(따로따로 순서대로 날짜를 증가시키면 다음번에 루머확인할때 오류!) q에 한번 더 담아서 돌려줘야 한다는 것만 주의하면 됐었다. #include #include #include using namespace std; vector v[200000]; int rumor[200000] = { -1, }; int n; int count_rumor(int x) { int cnt = 0; for (int i = 0; i < v[x].size(); ++i) { if (rumor[v[x][i]] != -1) { c..

다익스트라 알고리즘을 처음 배우고 풀었던 문제였다. 다익스트라만 적용하면 금방 풀리는 쉬운 문제였다..! #include #include #include #include using namespace std; int answer[20001];//최소 비용 vector line[300001];// 간선 int INF = 2000010; void dijstra(int start) { answer[start] = 0; priority_queue pq; pq.push(make_pair(0, start)); while (!pq.empty()) { int current = pq.top().second; int distance = -pq.top().first;//최소 힙으로 변환 pq.pop(); if (answer[..

너무 어려웠다... 초등부 3번 문제라는데...하 그리디 문제에 대해서 더욱 공부해볼 계획이다. #include #include using namespace std; int arr[1001]; int dp[1000000]; int main(){ int n; int sum=1; cin>>n; for(int i=0; i>arr[i]; } sort(arr, arr+n); for(int i=0; i sum){ break; } sum+=arr[i]; } cout

이 문제는 대회 당시에 시간초과로 시간을 많이 잡아먹었는데 대회가 끝나고 자료구조를 set으로 바꿔서 해보니 한번에 통과되어서 상당히 현타가 왔던 문제였다.... #include #include #include #include using namespace std; string s, e, q; set st; long long Change(string s) { string si = s.substr(0, 2); string boon = s.substr(3,2); return 60 * stol(si) + stol(boon); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s >> e >> q; string str, name; int cnt = ..

신촌 ICPC대회에 나왔던 문제이다. 처음에 LIS문제인가 싶어서 만만히 보고 덤볐다가 여러번 시간을 날리고.. 두 포인터문제라는걸 알게되니 금방 풀렸다..! //20922 #include #include #include using namespace std; int n, k; int arr[200001]; int visited[200001]; vector v; int answer; int l, r; int main() { cin >> n >> k; for (int i = 0; i > arr[i]; } visited[arr[0]] = 1; l = r = 0; while (l

전형적인 dp문제 중 한문제였다. 위에서 내려올때와 옆에서 올때의 두가지 경우로 dp[i][j]가 결정된다. #include #include #include using namespace std; int arr[301][301]; int dp[301][301]; int k; int main() { int n, m; cin >> n >> m; for (int i = 0; i > x >> y; arr[x][y] = m - (x + y); if (arr[x][y] < 0) { arr[x][y] = 0; } dp[x][y] = arr[x][y]; } for (int i = 1; i < 300; ++i) { for (int j = 1; j < 300; ++j) { d..