qjatn0120

A. We Need the Zero code 길이가 \(N\)인 배열이 주어진다. 이제 이 배열의 모든 값에 특정 \(x\)를 XOR해서 배열의 모든 원소를 XOR한 값이 0이 될 수 있는지 확인하고 싶다. 가능하면 XOR 결과가 0이 되도록 하는 \(x\)를, 불가능하면 -1을 출력해야 한다. XOR을 많이 다뤘다면 빠르게 풀 수 있는 문제이다. XOR의 가장 큰 특징은 \(a \oplus x \oplus x = a\)라는 점이다. 일단 처음 주어진 배열의 모든 원소의 XOR값을 \(A\)라 하고, 모든 원소에 \(x\)를 XOR하자. 만약 \(N\)이 짝수라면 모든 원소의 XOR값은 여전히 \(A\)일거고, \(N\)이 홀수라면 XOR값은 \(A \oplus x\)가 될 것이다. 따라서 \(N\)이 ..

A. Garland code 색깔이 있는 전구가 4개 주어진다. 4개의 전구는 모두 꺼져있다. 각 전구의 색깔은 0이상 9이하의 정수로 표현된다. 이제 4개의 전구를 하나씩 스위치(킨 전구를 끄거나 꺼져있는 전구를 키는 것)해서 모두 킬 것이다. 그런데 연속해서 같은 색깔의 전구를 스위치할 수는 없다. 최소 몇 번의 스위치를 해야 모든 전구를 킬 수 있는지 출력하면 된다. 만약 모든 전구를 킬 수 없으면 -1을 출력하면 된다. 일단 모든 전구의 색깔이 같으면 모든 전구를 킬 수 없다. 만약 세 전구의 색깔이 똑같고 나머지 하나가 다르다면, 총 6번 스위치를 해야 모든 전구를 킬 수 있다. 그 이외의 경우에는 4번의 스위치만으로도 모든 전구를 킬 수 있다. 따라서 모든 전구의 색깔이 같으면 -1, 세 전구..

A. Plus or Minus code \(a\), \(b\), \(c\)가 주어진다. \(a + b = c\) 또는 \(a - b = c\)를 만족한다. 둘 중 어느것을 만족하는 지 출력하면 된다. 문제에서 시키는대로 하면 된다. B. Grab the Candies code \(N\)개의 가방이 있고, \(i\)번째 가방에는 \(a_i\)개의 사탕이 있다. 이제 가방을 특정한 순서대로 열 것이다. 만약 가방에 짝수 개의 사탕이 있다면, Mihai가 그 가방에 있는 사탕을 모두 가진다. 반대의 경우에는 Bianca가 모두 가져간다. 이제 가방을 여는 순서를 잘 배열해서 처음부터 모든 가방을 열 때까지 항상 Mihai가 Bianca보다 사탕을 많이 가지고 있도록 하게 하고 싶다. 가능하면 Yes, 불가능하..

A. Medium Number code 문제 설명 3개의 수를 입력받아 중앙값을 출력해야 한다. 알고리즘 세 수를 정렬하고, 2번째 숫자를 출력하였다. B. Atilla's Favorite Problem code 문제 설명 주어진 문자열을 적을 때, 1번째 알파벳인 a부터 몇 번째 알파벳까지 사용해야 하는지를 출력해야 한다. 알고리즘 문자열 \(s\)에 있는 모든 문자 \(c\)에 대해 \(c - 'a' + 1\)의 최댓값을 출력하면 된다. C. Advantage code 문제 설명 길이가 \(n\)이고 각 원소가 정수인 배열이 주어진다. 모든 원소에 대해 자신에서 자신을 제외한 값들 중 최대인 값을 뺀 결과를 구해 출력해야 한다. 알고리즘 먼저 최댓값을 가지는 원소를 하나 찾는다. 해당 원소를 제외한 ..

A. Indirect Sort code 문제 설명 길이가 \(n\)이고 1부터 \(n\)까지 한 번만 등장하는 배열이 입력으로 주어진다. \(1\le i a_k\)이면 \(a_i\)에 \(a_j\)만큼 더하고, 그렇지 않다면 \(a_j\)와 \(a_k\)를 swap한다. 여러 번의 연산을 통해 배열을 오름차순으로 정렬할 수 있는지 여부를 출력해야 한다. 알고리즘 이 문제는 배열의 첫 번째 원소에 집중하면 빠르게 풀 수 있다. 먼저 배열의 첫 번째 원소가 1이라 가정하자. 그렇다면 \(i = 1\)을 고르면, 두 번째 원소부터 마지막 원소까지 원하는 대로 변경할 수 있어 무조건 바꿀 수 있다. 하지만 첫 번째 ..

A. PassWord code 문제 설명 0부터 9까지의 숫자 중복 허용하여 4개를 사용해 만들 수 있는 비밀번호의 수를 출력해야 한다. 이때, 비밀번호는 서로 다른 숫자를 2개씩 포함해야 하고, 사용하지 않아야 하는 숫자들도 주어진다. 알고리즘 총 10,000가지의 조합을 하나씩 검사해보며 문제의 조건을 만족하는 지 확인해보면 된다. B. Permutation Value code 문제 설명 길이가 \(n\)인 순열 \(a\)에 대하여 이 순열의 값을 연속된 부분 배열이 순열인 부분 배열의 개수로 정의된다. 순열의 값이 최소가 되도록 하는 순열을 출력해야 한다. 알고리즘 먼저 순열의 값은 최소 2라는 것을 쉽게 발견할 수 있다. [1]과 \(a\), 이렇게 2개의 부분 배열이 순열인 경우가 2가지 존재한..

A. Sum code 문제 설명 세 정수 a, b, c가 주어진다. 한 수가 다른 두 수의 합이 될 수 있는지 여부를 출력하면 된다. 알고리즘 if문을 3번 써서 검사하면 된다. B. Increasing code 문제 설명 정수로 이루어진 배열이 주어진다. 이 배열의 원소를 잘 재배치해 strictly increasing을 만족하도록 할 수 있는지를 출력하면 된다. 알고리즘 배열을 정렬한 후에 이웃한 원소 중 같은 게 있는지를 보면 된다. C. Stripes code 문제 설명 8x8의 판에 빨간 가로선과 파란 세로선을 번갈아서 긋는다. 원래 색깔이 있던 칸에 또 칠하면 덮어 씌워진다. 여러 번 색칠한 판의 상태가 주어졌을 때, 마지막으로 칠한 선의 색깔을 출력해야 한다. 알고리즘 빨간 선과 파란 선은 ..

A. Ela Sorting Books code 문제 설명 길이가 \(n\)인 문자열이 주어지고 이를 \(k\)개의 그룹으로 나누고자 한다. \(k\)는 \(n\)의 약수이다. 이제 이 \(k\)개의 그룹의 mex인 알파벳을 구하고 이 알파벳을 나열하여 길이가 \(k\)인 문자열을 만든다. 만들 수 있는 문자열 중 사전순으로 가장 느린 문자열을 출력해야 한다. 알고리즘 먼저, \(k\)개의 그룹을 만들어놓고 여기에 알파벳을 순서대로 할당하는 방식으로 풀어보자. 알파벳 a를 고려해보자. 사전순으로 가장 느리게 만들기 위해서는 a를 맨 앞에 있는 그룹부터 순서대로 넣어줘야 한다. 만약 a의 개수가 \(k\)보다 많다면 남는 a는 아무데나 넣어도 된다. 이는 알파벳 b, c, ... 에 대해서도 성립한다. 따라..

A. Colored Balls: Revisited code 문제 설명 \(N\)종류의 공이 각각 \(cnt_i\)개씩 있다. 총 공의 개수는 홀수 개이다. 여기서 서로 다른 색깔은 가진 두 공을 계속 없애나갈 것이다. 그렇다면 마지막에는 같은 색깔을 가진 공만 남을 것이다. 이때, 남은 공의 색깔로 가능한 색깔 중 하나를 출력하면 된다. 알고리즘 만약 한 색깔의 공이 \(\frac{N + 1}{2}\) 개 이상 있다면, 맨 마지막에는 무조건 그 색깔의 공이 남게 된다. 다른 색깔인 공의 개수를 모두 합쳐도, 그 색깔인 공의 개수보다 더 작기 때문이다. 따라서 \(\frac{N + 1}{2}\)개 이상인 색깔의 공이 존재한다면, 그 색깔을 출력하면 된다. 그 이외의 경우에는 어느 공이든 남게 할 수 있다...

A. 2-3 Moves code 문제 설명 0번에서 \(n\)번으로 이동하려고 한다. 현재 위치가 \(x\)일 때, \(x+2\), \(x+3\), \(x-2\), \(x-3\)으로 이동할 수 있다. \(n\)번으로 이동하기 위한 최소 이동 횟수를 출력해야 한다. 알고리즘 일단 \(n\)이 1인 경우는 2칸으로 예외 처리를 하였다. 만약 \(n\)이 3의 배수가 아니라면, \(\frac{n}{3}+1\)번 이동해야 한다. 계속 3칸씩 오른쪽으로 이동하다가, \(n\)을 3으로 나눈 나머지가 1이면 2칸씩 2번, 나머지가 2이면 마지막에 2칸 1번을 뛰어야 하기 때문이다. \(n\)이 3의 배수라면 단순히 3칸씩 계속 뛰면 된다. 따라서 뛰어야 하는 횟수는 \( frac{n+2}{3}\)이 된다. \(n\..