본문 바로가기

전체 글

 (147)
백준 1462: 퀴즈쇼 https://www.acmicpc.net/problem/1462 이 문제는 예전에 해결한 문제지만, DP에 대한 시간복잡도를 고려하지 않았던 나에게 있어 좋았던 문제여서 이렇게 다뤄보려 한다. 이 문제의 첫 인상은 답답함이다. N이 최대 500,000이라서 그리디적으로 해결해야 할지 고민을 할 정도였다. 하지만 천천히 읽어보니 DP 사용이 적합해보였다. 처음 생각한 점화식은 다음과 같다. DP[idx][cnt] = max(DP[idx + 1][(cnt + 1 == M ? 0 : cnt + 1)] + score[idx] + (cnt + 1 == M ? bonusScore[idx] : 0), dp[idx + 1][cnt]) 하지만 처음에 얘기한 듯 이 문제의 N이 너무 커서 이런 점화식을 잡으면 500,0..
백준 1082: 방 번호 https://www.acmicpc.net/problem/1082 일단 문제를 보아하니 DP 문제인 것 같다.내가 DP 문제를 풀 때 먼저 생각하는 것이 있다. "일단 먼저 가보자, 그리고 그 상태를 숫자로 나타내서 결과값을 저장하자"이다. 이러한 방식으로 나는 플레티넘 DP 문제도 해결해왔다. 그런데, 이 문제는 뭔가 다른 것 같다. 아무리 생각해도 이전에 고른 숫자를 DP하는 방법이 떠오르지 않았다. 최대 숫자가 long long 타입을 넘을 위험성이 있어서, string 타입을 사용해야하는데, 이것을 DP 배열의 인덱스로 바꾸는 법이 도저히 떠오르지 않았고, 해쉬테이블 사용은 불안했다. 결국 나는 생각을 전환하기로 한다. DP에서 벗어나서, Greedy한 생각으로 방침을 바꾸기로. 이 문제에서 최대..
백준 13018: 특이한 수열 https://www.acmicpc.net/problem/13018  이 문제 역시, 봤을 때부터 막막했다. 이걸 어떻게 접근을 해야할까, 고민을 하였다. 문제를 읽고, 천천히 생각을 해보며, 어떻게 해결을 하면 좋을까... 문득, 나는 이 문제를 다르게 생각하기로 결심한다. 이 문제는 수열이기 때문에 1~n이 딱 한 번씩 나온다. 인덱스도 1~n까지 있다 그렇다면, 1~n까지의 수가 1~n까지의 일대일 대응을 찾는 문제로 전환할 수 있을 것이다란 생각이 들었다. n이 7일때, 대략적인 그림은 다음과 같다.이제 생각을 전환했으니 답을 찾아야한다. 이렇게 전환을 해보면 브루트포스를 사용하고 싶지만, N이 100000이라서, 사용을 할 수 없다. 일단 극단적인 케이스를 살펴보며 답을 구하는 법을 연구를 해보..
백준 14370: 전화번호 수수께끼(Large) https://www.acmicpc.net/problem/14370  이번엔 재밌는 문제를 해결해보자. 이 문제를 읽고나면 처음 떠올리는 해결책은 브루트포스이다. 하지만, S의 길이가 3 이상 2000 이하이므로 이 문제의 해결책은 아니다. 정확히는 https://www.acmicpc.net/problem/14369백준 14369: 전화번호 수수께끼(Small)의 정답에 가깝다.다만, 이 문제의 해결책으로도 14369 또한 해결할 수 있다! 이 문제를 읽었을 때, 나는 머리가 순간 백지가 되었다. 도대체 어떻게 이 문제를 해결해야 할 지 감이 전혀 잡히지 않았었다. 그렇지만, 마음을 다잡고 숫자의 영어들을 쭉 살피었고, 알아낸 것이 하나 있었다. 0~9의 영어 숫자 중에 유일한 알파벳을 가지는 숫자가 있..
백준 1533: 길의 개수 https://www.acmicpc.net/problem/1533이 문제를 풀기 위해서는 https://www.acmicpc.net/problem/12850이 문제 부터 해결해야한다.위의 문제의 해결법은https://sumserv.tistory.com/92 백준 12850: 본대 산책2https://www.acmicpc.net/problem/12850 이 문제는 보자마자 어떻게 풀어야 할 지 막막했다. 태그는 "분할 정복을 이용한 거듭제곱"인데, 이거를 어떻게 사용해야할 지 감이 전혀 잡히지 않았다. 그럼에도sumserv.tistory.com이전에 다뤘으므로 생략한다. 큰 차이점은 가중치가 생겼다는 점이다. 이전 문제에서는 있다 없다를 길로 표현했는데, 가중치가 생겨서, 단순하게 행렬의 곱셈으로 풀기엔 ..
백준 15944: 성공 https://www.acmicpc.net/problem/15944 이 문제는 예전에 푼 문제지만, 내가 직접 풀이를 생각했고, 아이디어가 재밌어서 지금도 기억이 나는 문제이기에, 이번에 다뤄보려고 한다. 이 문제를 처음 봤을 때는 Bruteforce 내지 Backtracking이 생각이 난다. 하지만, N과 M이 각각 500이라서 이것을 전부 Backtracking을 하려면 시간이 엄청 오래걸릴 것이다. 그럼 어떻게 해야할까? 일단 BFS를 사용하고, 장애물에 막히면 이 장애물을 폭파시키는 방식은 어떨까?그럼 어딜 폭발시키지? 마주한 장애물을 부수는 경우에 수도 여러가지인데, 이것도 Backtracking을 할것인가?만약 중간에 폭탄을 터트리는 경우가 최소 폭파의 횟수면 어떡하지? 이런저런 생각을 했고..
백준 1407: 2로 몇 번 나누어질까 https://www.acmicpc.net/problem/1407 이 문제는 처음 봤을 때, 구간의 끝 값을 2로 나눠서 어떻게 해볼 수 없을까? 부터 생각을 하였다.하지만, 아무리 끝 값을 이것저것 굴러보아도 답이 나오지 않아서 포기하려던 찰나 다른 문제에서 해결했던 방법이 떠올랐다. 바로 누적합이다. 이전까지 누적합은 배열 내에서만 사용을 했었는데, 이전에 풀었던 문제 중에 숫자 구간 합을 누적합을 이용해 해결했었던게 인상깊었던 문제가 있었다. 즉, [A, B] 구간의 합을 ([1, B] 구간의 합) - ([1, A - 1] 구간의 합) 으로 바꾸는 것이다. 그렇다면 이 문제도 이렇게 해결 할 수 있을 것이다. 그럼, [1, A] 구간의 합을 어떻게 구할 수 있을까? 나는 여기에 직면하게 된다. 규칙..
백준 23844: 트리 정리하기 이번에 푼 문제는 이것이다.https://www.acmicpc.net/problem/23844 이 문제의 메인 아이디어 자체는 금방 떠올렸다. 해당 노드를 포함한 자식노드의 수가 가장 작은 노드를 지운다란 아이디어였다. 그래서,  일단은 시도를 해보았다.#include #include #include #include using namespace std;vector adj[10001];int N, K, A, B, cnt[10001];queue q;bool v[10001], E[10001];int dfs(int here){ int& ret = cnt[here]; if (ret >= 0) return ret; ret = 1; for (int i = 0; i = 0) continue; ret += dfs(th..

티스토리툴바