kth990303의 코딩 블로그

추천받은 문제 중 하나. 문제는 아래와 같다. https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 의식의 흐름 및 해설 처음엔 평범한 knapsack인줄 알았는데, 생각해보니 자전거를 탈지, 도보로 갈지 선택을 해야되기 때문에 모든 경우를 선택하는 문제가 아니므로 knapsack dp가 아니었다. 따라서 top-down이든, bottom-up이든 시간복잡도 상 큰 차이가 없기 때문에 탑다운으로 풀었으며, N..

스터디그룹 채점현황 둘러보다가 발견한 문제. 결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다. 문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1325 sync_with_stdio(0); cin>>n>>m; while(m--){ int a,b; cin>>a>>b; v[b].push_back(a); } int M=0; for(int j=1;j>a>>b; v[b]...

적당히 어려워보이면서 문제 이해가 쉬운 문제 찾다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/12969 12969번: ABC 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. www.acmicpc.net N N >> K; memset(d, -1, sizeof(d)); if (!K) { for (int i = 0; i < N; i++) { cout

백준 잔디 채우려고 G4..G2 티어 중 랜덤하게 뽑아본 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14452 14452번: Cow Dance Show After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet "Cowpelia". The only aspect of the show that remains to be determined is the size of the stage www.acmicpc.net 여기서 제일 중요한 점! 소 ..

오랜만에 가벼운 문제로 백준 포스팅을 들고와보았다~! 문제는 아래와 같다. https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호 관련 문제는 언제나 재밌다 재미는 개뿔...ㅠㅠ 의식의 흐름 및 해설 1. O(N^2) dp 괄호를 보면 보통 나는 stack을 떠올리는데, 이 문제는 경우의 수를 묻기 때문에 바로 dp를 떠올릴 수 있었다. 괄호 개수에 따라 충분히 메모이제이션이 가능하다는 사실은 한눈에 보이기 때문. 일단 N이 상당히 작은 데다가..

제목이 뭐 이리 길어 문제는 아래와 같다. https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 이걸 A번으로 생각하시다니... wookje님이 워낙 god이시긴 하지만 이럴 땐 진짜... 말잇못 나만 모르는 웰노운 소재가 있어서 기록해두는 문제. 의식의 흐름 및 해설 대체 직사각형을 어떻게 할 지 한참 고민했다. 일단 일렬로 나열된 트리노드들의 x값, y값을 어떻게 비교할지조..

스터디그룹에서 연습 C번으로 진행된 문제. 어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 의식의 흐름 및 해설 물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제. 이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난..

*주의* 정해와 다르게 해결하였으며, 정해 풀이는 올리지 않습니다. 스터디그룹 연습에서 B번으로 나온 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 의식의 흐름 및 해설 문제 이해가 조금 힘든데, 쉽게 풀이하자면 모든 포지션에 한 명 이상의 선수가 위치해야 된다. 모든 포지션에 선수가 위치해야 되므로 TSP와 똑같다. 그러므로 이 문제와 거의 유사하다. https://kth990303.tistory.com/61 [BOJ] 백준 1311. 할 ..

스터디그룹에서 진행한 연습 중 A번으로 나왔던 문제. 문제가 굉장히 긴데, 실생활에서 흔히 마주칠만한 좋은 문제였다. https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 의식의 흐름 및 해설 스키를 못타는 날이 중간에 껴 있더라도 이용권을 사용할 수 있어 문제 난이도가 낮아진 느낌. 만약 이런 조건이 없었다면 case_work가 좀 더 빡세졌을 것 같다. N이 100이기 때문에 시간복잡도가 상당히 널널하다. 현재 날짜에 스키를 탈 수 있다면 1일권, 3일권..

작년에는 사정 상 GoodBye, BOJ 2020! 을 참여하지 못했고, 나중에 연습삼아 풀어본 결과 1솔밖에 못하는 결과를 얻었다. 그래서 이번 GoodBye, BOJ 2021!에선 몇솔을 하든 상관없이, G3~2 까지의 문제들은 전부 해결해보는 것을 목표로 응시하였다. 프로징 전에 A~D 4솔, 프로징 후에 E를 시도했으나, 구현미스가 나서 5솔하지 못한 채 4솔로 마무리하였다. 결론적으론, 총 4솔로 마무리했다. 패널티가 좀 있기도 하고, E번을 해결하지 못했기 때문에 최종등수는 90등대이지 않을까 싶다. +) 22.01.01. 추가 확실히 E가 어려웠던 것 같다. 84등의 좋은 성적을 거두었다 ㅎㅎ 확실히 1년 전에 비해 많이 성장했음을 느끼는 계기가 된 대회였다 ㅎㅎ 간단하게 문제 별 느낀 점 ..