kth990303의 코딩 블로그

대회 오픈컨 당일에 사정상 참여할 수 없어 뒤늦게 시간재고 풀어보는 시간을 가졌다. 오픈컨은 7시간동안 15문제였던 것으로 기억하는데, 7시간 내내 ps에 시간투자하긴 어려울 듯하여, 14~17시동안 Master 8문제를 해결해보는 시간을 가졌다. 진행 방식: 그룹 연습 / 티어: 성공한 문제에만 표시 / 알고리즘 분류: 보지 않음. / 그 전에 해결한 문제: 없음. 오픈컨 참가한 사람들에게는 solvedac 캐릭터가 판교역 옆에 서있는 배경을 주던데, 나는 오픈컨 참여는 하지 못했기 때문에 받지 못했다. 간단하게 후기를 작성해보겠다. 23738. A - Ресторан 대문자로 이루어진 문자열을 입력받으면 소문자로 바꿔주되, 특정 문자는 별도로 replace해주어야 하는 문제였다. 크게 어렵지 않은데,..

재밌는 문제가 뭐있을까 둘러보다가 발견한 문제. 마침 우리 학교에서 푼 사람이 아무도 없기도 해서 랭작용으로도 좋을 듯 해서 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/11877 11877번: 홍수 용량이 정확히 X인 히스토그램을 만들 수 없다면 첫째 줄에 -1을 출력해라. 그렇지 않다면 용량이 X가 되는 히스토그램의 열 h1, h2, …, hN를 출력해라. 그러한 방법이 여러 개가 있다면 아무 것이 www.acmicpc.net 문제 해석이 조금 껄끄러울 수 있는데, 쉽게 말해서 1~N까지의 높이로 이루어진 기둥들만으로 히스토그램을 만들되, 양옆 높이가 자신 높이보다 낮을 경우 물이 새므로 불가능하며, 맨 끝쪽에는 물이 없어야 한다는 소리다. 의식의 흐름 ..

이번에도 UCPC 문제 포스팅이다. 트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17365 17365번: 별다줄 먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문 www.acmicpc.net 의식의 흐름 및 해설 예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다. 해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*..

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다. 기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 의식의 흐름 및 해설 먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다. 마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 ..

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다. (아래 포스팅 참고) https://kth990303.tistory.com/207 [Knapsack] 냅색은 웬만해선 바텀업으로 짜자 knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. kth990303.tistory.com 이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다. knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다. 이 ..

학교랭킹 랭작을 위해 풀은 문제인데, 꽤나 아이디어 면에서 얻어갈 게 많았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17038 17038번: The Great Revegetation (Silver) A lengthy drought has left Farmer John's $N$ pastures devoid of grass. However, with the rainy season arriving soon, the time has come to "revegetate". In Farmer John's shed, he has two buckets, each with a different type of grass seed. He wants to plant g www.acm..

재밌어보이는 그래프 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/2311 2311번: 왕복 여행 첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 www.acmicpc.net 의식의 흐름 및 해설 1->N->1로 돌아가는데, 이미 방문했던 길은 방문할 수 없다. 일단 가중치가 존재하기 때문에 dijkstra나 binary_search를 적절히 이용해볼까 생각이 들었다. 그러나, dijkstra로 1->N까지의 최소 시간은 구한다 치나, N->1로 다시 돌아갈 때, 중복방문을 허용하지 ..

마찬가지로 solvedac 빼빼로 이벤트때문에 막대과자 얻으려고 둘러보다가 발견한 문제. 근데 정말 문제를 잘만드신 것 같다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 이 문제는 알고리즘 분류를 보지 말고 풀길 바란다. 오로지 알고리즘 분류를 떠올리는 난이도 때문에 티어가 올라간 문제라 생각된다. 의식의 흐름 및 해설 1번부터 시작해야되는데, 최소비용으로 접근해야 되니까 BFS를 생각해봤다. BFS는 간선 비용이 있기 ..

solvedac 빼빼로 이벤트 중, 막대과자가 부족해서 골드 문제 아무거나 랜덤으로 뽑아서 풀게 된 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22863 22863번: 원상 복구 (large) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 의식의 흐름 및 해설 문제가 정말 permutation_cycle(순열사이클)처럼 생겼다. 근데 K가 최대 1e15니까 K번 순열 사이클을 돌리는 단순한 풀이는 안되겠다. 순열..

엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제. 이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다. 위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데, 이번 기회에 복습 겸 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmi..