본문 바로가기

Problem Solving

(27)
[CodeUp 4035] 커피전문점 커피전문점 1. 첫째 줄에 트리의 노드(후보지)의 개수를 나타내는 정수 n이 주어진다. (2≤n≤100,000) 후보지는 1부터 n까지의 번호로 구분된다. 2. 둘째 줄부터 n-1개의 줄에 각 줄마다 후보지 쌍을 나타내는 두 codeup.kr 코드업을 밀던 중에 흥미로운 문제를 발견해서 포스팅한다. 다른 분들과 풀이의 방향이 달라 시간은 조금 느리지만, 다행히 코드는 깔끔하다. ㅎ 더보기 정해는 Union-Find 와 bfs 를 요구하지만, 사실 lca 만으로 풀린다! 생각의 편의를 위해 트리의 루트를 A로 만들어주자. 최적지의 집합이 (A-B 경로) $\cup $ (A-C 경로) 라는 것은 어렵지 않게 짐작 가능하다. 따라서 최적지의 개수는 $dep[a]+dep[b]-dep[lca(a,b)]+1$ 로 ..
[BOJ 20188] 등산 마니아 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 무난한 트리 DP라고 생각했는데 풀고 나니 DP를 쓰지 않았더라. 나처럼 푼 사람이 거의 없는 듯해서 풀이를 한번 소개해보려 한다. (어쩐지 어렵더라) 더보기 풀이의 전체적인 틀은 트리 dp할 때와 비슷하다. dfs를 돌면서 서브 트리에 대해 문제를 해결한 다음, 이를 합쳐서 전체 트리에 대한 문제를 해결한다. 하지만 이때 서브 트리에서 전해주는 값이 조금 다를 뿐이다. 다음과 같은 상황을 가정해보자. 깊이가 $d$인 노드 $p$를 루트 노드로 하는 서브 트..
Diamond I 달성 '다이아 2 달성' 글을 올린 지 대략 한 달 만에 다시 글을 쓰게 되었다. 시험 기간을 제외하면 2~3주 정도 걸린 것 같다. 내 solved.ac 히스토리를 보면 시험이 언제였는지 한눈에 찾을 수 있을 듯하다. 시험 기간 중에는 코딩을 거의 하지 않았지만 풀고 싶거나 배우고 싶은 문제와 알고리즘들을 따로 모아 두고 틈틈이 고민했다. 이 문제들을 시험이 끝나자마자 쭉 풀어버렸고, 그래서 레이팅이 급상승한 것 같다. (물론 아직 풀지 못한 문제들도 많다.) 마지막으로 푼 문제는 제곱수의 합 2 (More Huge)으로, 출제자가 소멤 블로그에 쓴 글을 참고하여 해결했다. 세 달 전에 제곱수의 합 (More Huge)를 해결했을 때부터 풀고 싶었고 최근에 학교에서 (개인적으로) 가우스 정수를 공부하고 나서..
1,200 1,000에서 1,100까지는 파이썬 기초 문제 덕분에 수월하게 올라갔다. 하지만 1,100에서 1,200까지는... 정말 오랜 시간 투자와 노력이 있었던 것 같다. 1,000문제 달성 글을 올린 날짜가 2월 15일이고, 파이썬 기초 문제가 나온 날이 2월 21일이니 1,200문제까지는 4개월 하고도 일주일 정도가 더 걸린 것이다. 그러나 보니 어느새 5위권을 눈앞에 둘 정도로 순위도 높아졌다. 이젠 정말로 풀 수 있는 문제가 얼마 남지 않았지만..ㅋㅋ 이대로 꾸준히 해서 3~4위 정도에 안착시킬 수만 있다면 행복할 것 같다. ps. 바로 어제, 평소처럼 코드업 게시판에 답변을 달던 중 정말 오랜만에(!) 재답변을 받을 수 있었다. 배열의 크기가 충분하지 않다는 것을 지적했었고, 이후 알려주셔서 감사하다..
[BOJ 2867] 수열의 값 2867번: 수열의 값 첫째 줄에 수열의 크기 N(2 n; vector sn(n+1),sx(n+1); ll x,ans=0; stack stn,stx; stn.push({0,0}); stx.push({(ll)1e9+1,0}); for(int i=1;i> x; while(stn.top().val>x) stn.pop(); while(stx.top().val