A. K-divisible Sum $n$과 $k$가 주어지면 $n$개의 아무 수를 더 해서 $k$의 배수를 만들고 싶은데, 그 $n$개의 수중 가장 큰 수의 값을 가장 작게 만들고, 그 수를 구하는 문제다. $n$보다 $k$가 작으면 성립하지 않으므로 $n$보다 크면서 가장 작은 $k$의 배수를 구해준다. $n$개의 수를 모두 1로 맞추면 $n$이 나오고, $n+1$은 1,1,1,1.....2, $n+2$는 1,1,1,1.....2,2, $n + (n - 1)$은 1,2,2,2,2....2 이므로 $t*n + alpha$에 대해 $alpha == 0$이면 $t$이고 $alpha != 0$이면 $t + 1$이다. $t*n + alpha = k$를 계산해주면 된다. B. Inflation 매 달의 물건의 가..
투포인터 [링크] [풀이] 전형적인 투포인터 문제이나, '중복'되지 않게 처리해주기 위해 처리해주는 것이 약간 까다롭다. 입력배열을 a + b형태로 더한 배열($10^6$개)과 c - d형태로 더한 더한 배열($10^6$개)로 만들어보자. 여기서 투포인터를 돌리면 끝이다. 다만, 유의해야할 점은 1. 두 수를 더해서 배열을 만들 때 두 수는 서로 달라야한다. 2. 음수도 입력으로 들어올 수 있기 때문에 $n^2$개를 모두 만들어 주어야한다. 2중 for문을 $i$ from $0$ to $n$, $j$ from $i + 1$ to $n$으로 돌리면 음수의 경우에 답이 나오지 않는다. 3. 배열을 만들 때 값만 저장하는 것이 아닌, index도 같이 저장해둬야 중복을 처리할 수 있다. 4. 중복처리는 투포인..
[문제] 7개의 음(pitch)으로만 구성된 악곡이 있다. 예를 들어 중세 그레고리안 성가는 7개의 음, 우리나라와 중국 일본의 민속 음악은 5개의 음으로 구성된 펜타토닉 음계를 사용한다. 음악에서 반복과 변형은 노래를 끌고 나가는 매우 중요한 동력 알고리즘이다. 반복이 너무 없으면 청중은 무료함, 지루함을 느끼지만, 또 너무 같은 상투적인 구조가 변화 없이 반복되면 긴장감이나 새로움이 떨어져 유치해지거나 쉽게 흥미를 잃게 된다. 이 문제에서 입력 음악은 7개의 소문자 {$c,d,e,f,g,a,b$}로 구성된 문자열로 표현된다. 이 문제에서 음의 지속을 나타내는 박자는 일단 무시하기로 한다. 어떤 구절이 반복된다는 것은 어떤 부분 문자열(substring)이 다른 위치에서 비슷한 모양으로 다시 나타난다는..
UNION-FIND MST(크루스칼) LCA와 응용 [링크] [풀이] 전체 풀이를 설명하면 MST를 먼저 만들고, 쓰지 않은 간선들을 하나 하나 탐색해가면서 그 간선을 추가하면 CYCLE이 생긴다. 무조건. 그러므로 CYCLE을 제거할 수 있는 MST의 간선을 하나 제거한다. 그랬을 때 나오는 스패닝 트리의 값의 최솟값을 찾으면 두 번째로 작은 MST의 값을 구할 수 있다. 이제 제거할 간선을 하나 찾아야 하는데, greedy하게 생각해보면 cycle에 있는 간선 중 가장 큰 간선을 제거해야한다. cycle은 lca를 구하면 MST의 cycle을 찾을 수 있다. 문제는 lca까지 가는 간선 중 최댓값을 구해야하는데, naive하게 생각해보면 dfs돌리면 되니 O($n$)이다. LCA를 구하는 과정에서 L..
전체적으로 쉬웠던 Round다. A. Space Navigation 상하좌우로 움직여야하는 명령 string이 들어왔을 때, 명령 중 아무거나 제거했을 때 목적지에 도달할 수 있는지 판단하는 문제다. 상의 개수, 하의 개수, 좌의 개수, 우의 개수를 전부 더하면 명령을 적절히 제거했을 때 움직일 수 있는 boundary가 나오므로 그 boundary내에 목적지가 있는지 판단하면 된다. B. New Colony 산이 일렬로 있는데, index 0 산에서 돌을 오른쪽으로 굴린다. 만약 높이가 더 높은 산을 만나서 돌이 멈추게 될 경우, 멈춘 그 산의 높이는 1 증가한다. k번째 돌을 굴렸을 때 그 돌이 멈추는 산의 index를 출력해야하는데, 더 높은 산을 만나지 못 해서 산 끝까지 가게 되면 -1을 출력하..
얼마전 LCS5 문제를 푼게 크게 작용했다. 딱 1점 남았었는데, class 7번에 까지 딱 1문제 남았었고, 에센셜 문제 하나 보자마자 maximalFlow생각나서 예전에 작성해놓았던 템플릿 이용해서 풀었다. 아직 전성기 시절 두뇌회전의 반도 못 따라가고 있으니 더 분발하자.. 제발
역대 최악의 성적이다. 그도 그럴것이, 낮에 백준에서 다이아2짜리 문제 푼다고 너무 고생해서 머리가 너무 아픈 상태였는데,어쩔 수 없이 진행했다.. 근데, 그럼에도 불구하고 결과를 보면 blue유지가 가능한 점수다. 확실히 요즘 blue는 예전 cyan인듯 하다. A. Yet Another String Game 영어 해석이 안 되서 너무 오래걸렸다. index가 짝수면 'z'에 가깝게, 홀수면 'a'에 가깝게 바꿔주면 된다. B. The Great Hero 직관적으로 공격력이 낮은 녀석부터 패줘야 최적의 답이다. 한 번 제출했는데 틀리길래 공격력 순이 아니라 한 녀석과 전투하는 동안 감소하는 총 체력순으로 패줘야하나? 싶어서 그렇게 접근해봤지만 fail. 나중에 보니 int overflow때문이었다. 집..
[개요] 3학년 1학기 텀 프로젝트 주제로 식당 테이블 예약 앱을 만들기로 했다. Demo앱처럼 지도 api 넣어서 지도위에서 마커 누르고 하는 것 보다, list형식으로 쭉 띄워주는게 훨씬 보기 좋고, 그게 맞는 방향이라 생각 해서 그 방식으로 진행하려 했다. 단순히 geolocator로 현재 위치를 뽑아오고, 그 위치를 google map api로 넘겨서 주변 식당 list를 쭉 뽑아온 뒤 작업을 하려 했는데 여러 가지 문제가 발생했다. [문제] 1. google map api에서 fetch해 올 수 있는 주변 식당 list는 최대 60개다. 최대 60개라고는 하지만, test해보니 40개 밖에 안 되는듯 하다. 사실상 40개면 이 api를 이용해서 앱 개발은 불가능 하다고 봐야한다. naver나 k..
A. Add and Divide $a $/=$ b$와 $b $+=$ 1$의 연산 2가지를 해서 $a$를 0으로 만들어야 할 때, 최소 연산 수를 구하는 문제이다. 간단하게, bfs돌리면 $log_2(a)$만에 풀린다. 8분이나 걸린 이유는 $b$가 1일때 때문에 살짝 멈칫했고, visited check 때문에 set을 쓴다고 좀 오래 걸렸는데, 사실 visited check할 필요도 없이 그냥 $log_2(a)$만에 풀린다. B. Replace and Keep Sorted 배열 $b_i$가 $a_i$와 $k$-닮음 이려면 $a_i, b_i$ 모두 단조 증가해야하고, 같은 길이를 가지며, 원소가 $1$~$k$여야 하며 모두 distinct하며 정확히 한 원소만 달라야 한다. 증가하는 배열 $a_i$와 범위..
무려... 3년전에 3개월동안 고생하다가 못 풀고 입대 후, 전역 하고 풀었다... 가히 인간승리가 아닐 수 없다. [링크] [풀이] 머릿속에 맴돌던 아이디어는 딱 하나다. 아 이거 napsack dp같은데... dp테이블 하나의 값을 얻기 위해 필요한 정보는 1.현재 남은 날짜, 2.이제 선택할 레벨의 캐릭터, 3.남은 현재 선택할 레벨 캐릭터의 개수 라고 생각했다. $n$이 매우 작으니 dp table을 이렇게 구성해보았다. $dp[i][j][k]$는 $i$일 남았고, $j$레벨을 선택할 때, $k$개의 "더"캐릭터가 있을 때 "더" 얻을 수 있는 최대 레벨 로 구성했다. 여기서 "더"를 강조한 이유는, 문제에서 처음에 각 캐릭터가 얼마나 주어질지 언급이 없기 때문에, dp table에 그냥 캐릭터수..
