1과 0으로 구성된 문자열에 두 가지 연산을 할 수 있다. 인접한 두 문자의 자리를 바꾸거나, 인접한 두 1을 한 개의 1로 바꿀 수 있다. 이 문자열을 2진 숫자로 본다고 했을 때, 두 연산을 잘 사용하여 가장 작은 숫자로 바꾸어서 출력하는 문제이다.
인접한 두 문자의 자리를 바꾼단 말은 문자를 자유로이 움직일 수 있단 말과 같다. 따라서 모든 1을 왼쪽으로, 모든 0을 오른쪽으로 몰아넣으면 인접한 1은 한 개의 1로 바꿀 수 있으므로 1이 1개로 바뀔것이다. 더 이상 1을 없앨 수 없으므로 이때의 숫자가 가장 작은 숫자가 된다. 따라서 0의 개수만 세고난 뒤, 1 한 번 출력, 0의 개수만큼 0을 출력 해주면 된다.
예외가 하나 있는데 0이 들어오는 경우이다. 이때 1을 출력해주면 안되므로 예외처리를 해주어야한다.
B. Lara Croft and the New Game
배열의 row와 column인 $n, m$과 이동 횟수인 $k$가 주어진다. $k$번 이동 후 어느위치에 있는지 출력하는 문제다. 이동하는 패턴이 좀 특이한데, 먼저 $(1, 1)$에서 시작하여 $(n, 1)$까지 아래로 직선으로 쭉 내려간다. 그 다음, $(n, n)$까지 오른쪽으로 쭉 이동한다. 그 다음 한칸 올라가서 $(n - 1, 2)$까지 왼쪽으로 쭉 이동하고, 다시 한칸 올라가서 오른쪽으로 쭉 이동한다. 모든 칸을 방문했으면 멈추는데, 멈추는 지점은 무조건 $(1, 2)$이다.($n$이 짝수이므로)
간단한 문제다. $k$가 $n$보다 작으면 $(1, k)$번째 위치에 있다. $n$보다 클 경우 $k$를 $n$만큼 뺀 뒤(이 만큼 이동했으니까) column이 $m - 1$인 배열을 문제에서 주어진 이동방식대로 이동한다고 생각하면 된다. 학교 언어수업 과제로 나올법한 문제니 설명은 pass
학교 수업 과제로 나올법한 문제라서 뚝딱뚝딱하고 제출했는데 틀려버렸다. 문제를 잘 읽자. 문제에서 long long쓰라고 얘기해준다.
어떠한 범위를 나타내는 pair가 $n$개 주어진다. 그 범위들 중에 어떤 범위가 다른 범위를 포함하고 있으면, 그런 여러 녀석들 중 아무거나 하나의 두 index를 출력하는 문제다.
pair.first는 오름차순, pair.second는 내림차순으로 sorting하고, 첫 번째 녀석부터 for-loop를 돌며 pair.second값의 최대값을 저장해둔다. 이 최대값 보다 pair.second가 작거나 같을 경우 그 녀석이 어떤 범위에 포함되므로, 두 index를 출력해주면 된다.
BOJ-신입 사원 문제하고 똑같은 문제다. 신입 사원 문제를 기억하는 이유가 BOJ-굉장한 학생 이 문제 때문이다. 비슷한 문제 같지만 전혀 다른 문제니까 segment 연습할 겸 다시 한 번 풀어보자.
이렇게 바로 기억하고 푸는 문제지만 한번 틀렸는데, 범위 경계값도 포함되는걸 생각 못 했다. 경계값이 포함되므로 pair.second를 내림차순으로 정렬해야한다.
배열 $d(d_1 ~ d_n)$이 주어진다. 이 배열은 어떤 graph의 각 vertex의 degree를 distinct하게 나타내어 정렬한 배열이다. 즉, graph는 $d_n$개 만큼의 vertex로 구성되어있다. 이 때, 이 graph를 출력하는 문제이다.
어렵다. 드럽게 어렵다.
답지 풀이를 한글로 그대로 옮겨보면,
$1.$ $n == 0$ 이면 1개의 vertex를 가진 graph다.
$2.$ $n == 1$ 이면 $d_1 + 1$개의 graph를 가진 clique이다.
$3.$ 나머지 경우에는, 원소가 $k - 2$개인 $(d_2 - d_1, d_3 - d_1, ..... , d_{k - 1} - d_1)$배열의 값을 가진 graph(이하 subgraph)에 degree가 0인 $d_k - d_{k - 1}$개의 vertex를 추가하고, 지금까지 추가된 모든 vertex에 edge를 발사하는 $d_1$개의 vertex를 하나하나 차례로 추가하면 된다.("하나하나"의 의미는 첫 vertex를 추가하고, 다음 vertex를 추가할 때 첫 vertex에도 edge를 발사해야한단 소리다.)
자. $d_1$개의 vertex를 하나하차례로 추가하면, subgraph에 해당하는 배열의 값이 $(d_2, d_3, ~ , d_{k - 1})$로 변할 것이다. 그리고 degree가 0인 $d_k - d_{k - 1}$개의 vertex는 edgree가 $d_1$개가 될것이다. 마지막으로 $d_1$개의 모든 vertex로 edge를 발사하는 graph는 degree가 $d_k$가 될것이다. 따라서, $(d_1, d_2, ~ , d_k)$의 배열이 완성되며, $(d_{k-1} - d_1 + 1) + (d_k - d_{k-1}) + d_1 = d_k + 1$로, vertex의 개수가 $d_k + 1$개가 되어 모든 조건을 만족한다.
그래. 풀이는 이해했다. 그런데 당최 어떻게 이런 생각을 해내는지 궁금하다. 어떤 근거로 이런 풀이가 나왔는지 설명도 없다. 그냥 이렇다~만 언급한다. 아직 부족한가보다
$n$개의 몬스터의 $hp$와 $dmg$가 주어진다. 몬스터에게 총 첫 번째 마법을 총 $a$번, 두 번째 마법을 총 $b$번 쓸 수 있다. 첫 번째 마법은 지정한 몬스터의 $hp$를 2배하는 마법이다. 두번째 마법은 지정한 몬스터의 $dmg$를 $hp$와 똑같은 값으로 바꾸는 마법이다. 마법을 굳이 다 쓸 필요는 없다. 어떻게 마법을 쓰고 난 뒤, 모든 몬스터의 $dmg$의 합의 최대값을 출력하는 문제이다.
몇 분만 생각해보면 $a$마법은 무조건 한 녀석에서 몰빵해주는게 최대값을 얻을 수 있는 방법이라는 걸 알 수 있다. 따라서, for-loop를 돌며 하나 하나 $2^a$를 곱해보며 최대값을 찾아보면 된다.
풀이는 간단하지만 생각보다 예외처리도 많고 까다로운 문제다.
첫 번째로, $a$를 쓸 녀석을 결정하는게 생각보다 까다롭다. 어떤 녀석에게 $a$를 쓰고 난 뒤 $(hp - dmg)$를 기준으로 정렬하여 max값 찾고, 다시 다음 녀석 에게 $a$를 쓰고 max값 찾고 하면 $O(n^2)$이다. 그래서, 나는 $a$를 쓸 녀석을 결정하고 난 뒤 $(hp - dmg)$를 기준으로 정렬하고 위에서부터 $b$개에게 $b$개를 쓰려고 했다.
여기서 까다로운점은 $a$를 미리결정할 경우 $a$를 쓸 녀석을 결정하는 기준은 증가폭이 가장 큰 녀석이어야 할 것이다. 마법 $a$를 쓰지않고 $b$만 쓸 경우를 생각해보자. $b$를 쓸 녀석은 $(hp - dmg)$가 큰 녀석부터 나오도록 정렬하여 $b$개를 사용하면 될것이다.(물론 $(hp - dmg)$가 0이상일 때에만 써야한다.) 여기서 $b$이하번째의 녀석들에게 $a$를 쓰면 $hp * 2^a - hp$가 증가폭이 될 것이다.
반면에, $b$초과번째 녀석들에게 $a$를 쓰면 $hp * 2^a - dmg$가 증가폭이 될것이다. 또한, 이런 경우에는 $b$마법을 안 쓸 예정이었던 녀석에게 $b$마법을 쓰므로 원래 딱 $b$번째이었던 녀석에게 $b$마법을 쓰지 못 할것이다. 따라서 이녀석의 값의 변화$(hp - dmg)$도 증가폭에서 빼주어야할것이다.
그런데 또 생각해보면 $hp$에 $2^a$배를 해줬는데 $b$번째 안쪽으로 못 들어갈경우가 있다. 근데 이런경우는 애초에 다른 녀석에게 $a$를 쓰는게 더 이득일것이므로 신경 쓸 필요가 없다.
문제 자체의 아이디어는 간단했던 문젠데 BOLD처리한 부분을 catch해내는게 생각보다 어려워서 많이 못 푼것 같다.
