본문 바로가기

전체 글

15900 나무 탈출 어떻게 풀지 그려봤을 때 트리의 높이의 합이 짝수면 형석이가 이기고 홀수면 성원이가 이긴다. 그래서 트리의 높이를 구하는 게 관건인데.. 생각 1 bfs를 쓰자 안 써서 써보고 싶었음.. 하지만 bfs를 쓰면 리프노드를 못 찾으니 리프노드까지의 길이를 알지 못한다. 생각 2 dfs 다음 노드가 존재하지 않으면 리프노드란 뜻이므로 리프노드를 찾을 수 있다. 그럼 리프노드의 길이의 합을 구할 수 있다 생각 3 그런데 이거 리프노드 길이의 합으로 생각 안 하고 그냥 전체 edge의 개수라고 생각하면 되지 않나??? 줄 수 세면 되는 거 아냐???? 아니었다고 한다 --미완-- 음... size가 0인거 출력해보니 1이 나온다. 왜지?? 나중에 찾아보기로 #include #include #include #inc.. 더보기
11058 크리보드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair; using iii = tuple; int main() { int n; scanf("%d", &n); vector dp(n + 1); dp[1] = 1; dp[2] = 2; d.. 더보기
12738 가장 긴 증가하는 부분 수열 3 생각주간에 가장 긴 증가하는 부분수열 문제 있는 거 보고 이번에는 NlogN으로 푸는 거 공부해서 적용해야겠다!! 싶었는데 합이 가장 큰 걸 구하라고 해서 다른 문제로 제출했다. 이 알고리즘 세 번 봤는데 세 번 다 이해 못해서 낑낑거리다가 드디어 이해했다. 이제는 좀 알겠음. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long .. 더보기
6612 개미의 이동 개미가 부딪히고 방향을 바꾸는 걸 다르게 생각해보면 통과한다고 볼 수 있다. 그러면 최대 길이를 구할 수 있는데 마지막 개미의 번호를 구하는 게 문제였다. 느낌 상 중간에 있는 개미가 가장 늦게 떨어질 것 같은데 그러면 R R R인 경우에는 어떻게 해야 하나 싶고. 고민하다가 이 분 글 보고 참고해서 문제 풀었다. codersbrunch.blogspot.com/2017/02/6612-andrew-ant.html 6612번: Andrew the Ant https://www.acmicpc.net/problem/6612 $O(ta\lg a)$ 두 개미가 부딪혔을 때, 두 개미 모두 방향이 바뀌므로 서로를 통과해서 진행한다고 봐도 된다. 이런식으로 생각했을 때 모두 떨어지는데까지 걸린 시간은 codersbrun.. 더보기
12026 BOJ 거리 어떻게 풀지 계속 고민하다가 앞자리 동기분의 도움을 받았다. 문제 보자마자 뭔가 dp의 느낌이 들었고 값이 반복되는 부분이 있어서 이걸 저장해야 겠다고 생각했는데 식을 어떻게 세워야 할지 감이 안 잡혔다. b -> O -> J 순서로 반복되기도 하고.. 그러다 힌트 받고 다시 고민해보았다. 이걸 반복문 한 번에 해결하려 하지 말고 반복문 두 번 써서 i가 B일 때 j가 O인 애들을 전부 업데이트 하는 식으로 해보라길래 이렇게 생각하니 어떻게 풀 수 있을지 감이 잡혔다. 그래서 풀이 방법 먼저 -1로 초기화를 한다. 위의 사진 보면 i가 1인 J는 0번째부터 이어지는 값이 아니기 때문에 계산하면 안되는데 이걸 어떻게 할지 고민하다가 기존에 -1인 값은 넘어가도록 코드를 짰다. 만약 값이 이미 차있다면 이전.. 더보기
[10774] 저지 왜이리 머리가 안 굴러가지?? 이전에 푼 문제인데도 시간 좀 걸렸음.. 한동안 안 푸니깐 머리 굳는 것 같아서 매일 한 문제는 풀어야 겠다고 생각했다. 문제를 보면 번호마다 옷이 하나밖에 없어서 옷이 맞는 사람이 있으면 바로 옷을 주는 게 무조건 좋다. 그래서 아직 안 준 옷이고 사이즈가 맞다면 옷을 줄 수 있다고 체크하고 그 체크한 개수를 세면 된다. 코드 : #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).e.. 더보기
1251 단어 나누기 [미완] - 세 부분으로 나눠야 한다 - 부분의 길이는 최소 1이어야 한다 - 부분을 뒤집어서 합친 글자가 사전순으로 앞에 와야 한다 가장 먼저 든 생각은 가장 작은 알파벳과 그 다음으로 작은 알파벳을 찾은 다음 그 둘을 기준으로 나누면 가장 작은 문자열이 되겠다 싶었다. 그런데 무조건 부분의 길이가 1이상이어야 하므로 가장 작은 알파벳의 탐색 범위를 0 - size - 2로 잡고 그 다음을 idx2 - size - 1로 구하려 했는데.. 틀렸네.. 조금 더 고민해봐야겠다 #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #d.. 더보기
14426 접두사 찾기 [미완] 으음 입력이 10000이라 n^2일테니 그냥 이중포운 돌리자! 싶었는데 접두사 비교하는 부분이 문제였다. 그래서 미리 접두사를 다 만들어놓으면 어떨까 싶었음. 이걸 미리 만들어두고 비교하는 방식으로 하면 되겠다 싶었는데 미리 만들어 둔 거 길이가 5000000 이만큼이어서 NlogN으로 했을 때 터져버리는 것 같다.. 으음... #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; us.. 더보기