A. Infinity Gauntlet인피니티스톤의 색깔이 입력으로 들어오면 앞으로 더 모아야하는 인피니티스톤의 이름을 출력하는 문제다. 넘어가자. B. High School: Become Human$x$와 $y$가 주어진다. $x^y$와 $y^x$의 값을 비교해야하는 문제다. $1 2, 2 -> 4, 5 - > 3, 1 -> 4, 5 -> 3 으로 graph를 만들 수 있고, (1, 2, 4) 와 (3, 5)가 사이클을 이룸을 알 수 있다. cycle내에서는 cycle의 크기 - 1 만큼 swap하면 정렬된 순열을 만들 수 있으므로 $n - 사이클의 개수$가 최소 swap횟수이다.최소 swap횟수를 알았으면 petr인지 Um_nik인지 알 수 있는데, 사이클의 개수 $k$라 하고, 먼저 $n$이 홀일 때..
A. Equator$\!$ 배열이 주어지면, 배열의 값을 더하다가 지금까지 더한 값이 배열값의 총 합 $/ 2$ 보다 크거나 같을때 그 index를 출력하는 문제이다. 설명필요없다. B. Students in Railway Carriage 일렬의 좌석이 주어지고, 컴공생과 체대생이 자리에 앉으려한다. 컴공생은 컴공생옆에 앉지 못 하며, 체대생은 체대생옆에 안지 못 한다. 이때 최대한 앉을 수 있는 학생수를 구하는 문제다. 앉을 수 있는 자리 component를 각각 보자. component의 크기가 짝수이면 아무렇게나 서로 건너 앉으면 된다. component가 홀수 이면 컴공생이나 체대생 중 많은 숫자먼저 앉고 건너 앉으면 최대로 앉을 수 있다. 자리가 *...*일때 $a, b$가 1, 2라고 하면 *..
A. Splits $\!$ 숫자 $n$이 주어진다. $n$의 영혼은 증가하지않는 양의 정수의 수열을 의미하고, 이 수열의 합은 $n$이다. 영혼의 무게는 영혼의 가장 첫 번째 원소(즉, 가장 큰 수)와 같은 원소의 개수를 의미한다. 이때, $n$의 영혼의 무게의 개수를 구하는 문제다. 문제를 딱 보고 이거 너무 어려운데? 생각했는데 예제를 보니 간단하게 풀린다는걸 알 수 있었다. 모든 수 $n$에 대해 무게가 1인 영혼은 무조건 존재한다. $[n]$의 수열이 있으니까. 무게가 2인 영혼은? $[n / 2, n / 2]$ 또는 $[n / 2, n / 2, 1]$이 있으면 있을 것이다. 무게 3.. 4.. 모두 마찬가지로 $[n / k .... n / k, 1,1...1,1,1]$로 만들 수 있다.(1은 $..
A. Row $\!$ 0과 1로 이루어진 string이 주어지는데, 1이 인접해 있거나 1을 인접하게 하지 않고 0 자리에 1을 넣을 수 있으면 No를, 그 외에는 Yes를 출력하는 문제이다. 문제에서 얘기한 대로 구현하면 된다. 문제에서 Yes인 경우를 "maximal"하다고 표현했는데 아마 이 표현때문에 많은 사람이 헷갈렸을 것이다.(물론 나도) 1이 최대로 포함되어있지 않은 경우도 문제조건만 맞으면 Yes를 출력하면 된다. 예를들어서 01010 같은 경우는 10101이여야 1이 최대가 되지만 01010에서 1이 인접하지않고, 또한 1을 넣을 수 없으므로 Yes다. B. Bus of Characters distinct한 배열과 0과 1로 이루어진 string이 주어진다. string을 순서대로 돌며 ..
A. Minimum Binary Number $\!$ 1과 0으로 구성된 문자열에 두 가지 연산을 할 수 있다. 인접한 두 문자의 자리를 바꾸거나, 인접한 두 1을 한 개의 1로 바꿀 수 있다. 이 문자열을 2진 숫자로 본다고 했을 때, 두 연산을 잘 사용하여 가장 작은 숫자로 바꾸어서 출력하는 문제이다. 인접한 두 문자의 자리를 바꾼단 말은 문자를 자유로이 움직일 수 있단 말과 같다. 따라서 모든 1을 왼쪽으로, 모든 0을 오른쪽으로 몰아넣으면 인접한 1은 한 개의 1로 바꿀 수 있으므로 1이 1개로 바뀔것이다. 더 이상 1을 없앨 수 없으므로 이때의 숫자가 가장 작은 숫자가 된다. 따라서 0의 개수만 세고난 뒤, 1 한 번 출력, 0의 개수만큼 0을 출력 해주면 된다.예외가 하나 있는데 0이 들어오는..
A. Pizza, Pizza, Pizza!!! $\!$ $n$이 주어지면 피자를 칼로 균등하게 $(n + 1)$조각 시키려한다. 칼은 피자 도우부분에서 시작해서 도우까지 또는, 중간에 멈출 수도 있고, 중간에서 시작해서 중간에서 멈출수도 있다. 단, 직선으로만 잘라야한다. 칼질횟수를 구하여라. 정말 간단하다. $(n + 1)$이 짝수면 그냥 중간을 쑥 쑥 지나가게 잘라버리면된다. 한번 중앙을 가로지르는 칼질을 반복하면 한번 칼질에 같은 크기의 피자가 2개씩 나오기 때문이다. $(n + 1)$이 홀수면 중앙을 가로지르는 칼질로는 피자를 균등하게 자를수가 없다. 그냥 중앙에서 시작해서 $(n + 1)$번 잘라야 모두 같은 크기로 자를 수 있다. 너무 간단해서 2줄코딩했는데 $n$이 0일때 예외가 생겨버린다...
A. Help Farmer$\!$ $A*B*C$의 값이 주어졌을 때, $(A + 1) * (B + 2) * (C + 2) - A * B * C$의 값의 최대, 최솟값을 구하는 문제이다. $A*B*C$의 값은 상수이므로 $(A + 1) * (B + 2) * (C + 2)$를 결정해주면 되는데, $A*B*C$의 값 $n$의 약수를 모두 돌아보며 $A$, $B$의 값을 결정해주면 된다. ($A$, $B$가 결정되면 $C$는 알아서 결정되므로 고려할 필요가 없다.)2중 for문 으로 해결되는데, 약수를 결정하고나면 그 반대 쌍도 $A$나 $B$값으로 고려하여 체크해봐야한다.(예제를 돌려보면 무슨 뜻인지 이해가 갈 것이다.) 문제는 이게 시간내에 돌아가느냐인데.. 약수결정에 O($sqrt(n)$)이 걸리고, 또 ..
1. suffix array설명은 갓-crocus 블로그가, lcp설명은 plzrun 블로그가 제일 정리가 잘 되어있다. 2. suffix array의 존재이유는 lcp를 위해 있다고 해도 과언이 아니다. 3. O($nlogn$)만에 구하는 알고리즘도 있다. O($nlog^2n$) 알고리즘보고 오 기수정렬이랑 비슷하다 생각했는데 역시 radix sort를 이용한단다. 자료구조수업때 한번 본 이후로 처음 보며 처음 써본다. 제대로 이해하기 위해서는 radix sort를 다시 봐야겠다. 설명은 plzrun 블로그. 4. lcp가 이용되는 대표적인 문제는 BOJ_가장 긴 문자열 이다. 한 문자열에서 두 번 이상 나오는 문자열을 포함하는 suffix는 suffix array에서 항상 인접하고, lcp의 정의에 ..
A. Paper Airplanes$\!$ $k$명의 사람이 각각 $n$개의 종이비행기를 접으려 하는데 종이 1장당 종이비행기 $s$개를 만들 수 있다. 한 묶음에 $p$개의 종이가 들어있는 묶음을 몇 묶음 사야 하는지 출력하는 문제이다. 단, 1장의 종이를 찢어서 두 사람에게 나누어 줄 수가 없다. 먼저 예제를 보자. $(k, n, s, p) = (5, 3, 2, 3)$이다. 장당 2개의 종이비행기를 만들 수 있고, 한 사람이 3개의 종이비행기를 접어야 하므로 한 명당 2개의 종이가 필요하다. 5명이므로 10개의 종이가 필요하게되고, 한 묶음당 3개의 종이가 들어있으므로 총 4묶음을 사야 10개의 종이를 구할 수 있다. 즉, (($n$보다 크면서 가장 작은 $s$의 배수 $*$ k) 보다 크면서 가장 작..
A. Aramic script$\!$ 입력으로 문자열이 들어오는데, 각 문자열이 가지는 문자의 집합의 개수를 세는 문제이다.예를 들어 a aa aaa의 각 문자 집합은 a로 동일하므로 1을 출력해야하며, a aa aaa ab abab abbbb 는 {a}, {a, b}로 2개이므로 2를 출력해야한다. 간단히 들어온 문자열을 정렬한 뒤, unique 함수로 문자를 중복없게 뽑아낸 뒤, set에 넣어주면 된다. 한 번 틀렸는데, unique함수가 sorted 상태의 stl만 받는 다는 점.. B. Mancala 14칸 짜리 판에 구슬이 들어있는데 (0개 이상), 1개 이상의 구슬이 들어 있을 경우, 그 칸의 구슬을 모두 뽑아서 오른쪽으로 1칸씩 이동하면서 그 구슬을 1개씩 넣을 수 있다. 모두 넣고난 뒤, ..
