[알고리즘] 2022 중앙대학교 CHAC

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다.

(푸는대로 업데이트 할 예정..)

 

A. 2의 보수

정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다.

 

입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음)

 

B. 조커 찾기

카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다.

- 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다.

- 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다.

 

문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는게 빠르다.

 

C. 영재의 징검다리

오징어게임에 나온 다리건너기게임에서 무엇이 강화유리인지를 알 때 끝까지 가는 방법의 수를 구하는 문제이다. 단, 이동할 때 현재 위치에서 바로 앞의 인접한 3개의 유리중 하나로 이동한다.

 

dp테이블을 이용해서 현재 위치로 오기 위한 방법의 수를 계속 업데이트 하면 된다. 업데이트 할 때는 이전 위치에서 현재 위치로 올 수 있는 방법의 수들을 더한다.

 

D. 또 전자레인지야?

조리시간을 입력받아 전자레인지의 버튼을 최소한으로 눌러서 시간을 정확히 맞추는 문제이다. 버튼은 10초, 1분, 10분, 조리시작이 있다. 조리시작버튼은 조리중이 아닐때 조리를 시작시키고 0초였다면 30초로 시작시킨다. 또한 조리중일땐 30초 추가시킨다.

 

시간을 초단위로 바꿔 그 시간을 $t$라고 하자

 

* Case 1) $t < 30$

10초를 여러번 눌러 $t$로 맞춘뒤 조리시작을 누르면 되므로 $\frac{t}{10}+1$이다.

 

* Case 2) $t = 30$

조리시작만 누르면 되므로 답은 $1$이다.

 

* Case 3) $t > 40$

이제 유명한 $600$원, $60$원, $30$원, $10$원짜리 동전이 있을 때 최소한의 동전을 사용해서 $t$원을 맞추는 문제가 되어 그리디하게 해결하면 된다. 다만 처음에 조리시작을 누르고 시간을 추가하면 30초 얻을 수 있기 때문에 이 때도 고려해주어야 한다. $t$, $t-30$중 더 적게 사용하는 방법이 답이다.

(어쩌다보니 대회에서 퍼솔을 했다.)

 

E. 귀찮은 해강이

연결돼있는 건물들이 주어졌을 때 수업을 모두 듣기 위해 건물에서 몇번을 나가야 하는지 구하는 문제이다.

 

분리집합을 구현하고 현재 수업건물과 다음 수업건물이 같은 집합에 있지 않은 개수를 구한다.

 

F. 명진이의 신년계획

WIP

 

G. 123456789점

노트가 $N$개인 리듬게임에서 Perfect $a$개, Great $b$개, Good $c$개, Miss $d$개를 받았을 때 점수는 $S = \lfloor 10^9 \cdot \frac{2a+2b+c}{2N}+a\rfloor$이다. $N, S$가 주어졌을 때 가능한 $(2a+2b+c, a)$쌍을 구하는 문제이다.

 

재밌는 수학문제였다.

우선 조건을 생각해보면 $a+b+c \le N$이다.

 

* Case 1) $b,c = 0$

$a$를 $N$까지 탐색하며 가능한 경우가 있는지 찾는다.

 

* Case 2) $b, c \not=0$

$S$를 조작해보자

$S -a = \lfloor 10^9 \cdot \frac{2a+2b+c}{2N}\rfloor$

$\rightarrow S-a \le 10^9 \cdot \frac{2a+2b+c}{2N} \lt S-a+1$

$\rightarrow \frac{2N(S-a)}{10^9} \le 2a+2b+c \lt \frac{2N(S-a+1)}{10^9}$

이를 만족하는 $0$이상의 정수 $2a+2b+c$가 존재해야 한다.

부등식에서 왼쪽을 $L$이라하고 오른쪽 $R$이라고 할 때 존재하는 경우는 다음과 같다.

- $L$이 정수일 때

- $R$이 정수가 아니고 $\lfloor R \rfloor-\lfloor L \rfloor = 1$일 때(가능한 값이 $0, 1$중 하나이다.)

그 외에는 해가 존재하지 않는다.

(파이썬에서 math.floor안쓰고 int쓰다가 여러번 틀렸다.)

 

H. 푸앙이와 별

WIP

 

I. 말해 xor NO!

배열 $a$와 $b$가 있고 각 배열에서 원소를 하나씩 뽑아 xor연산을 했을 때 $k$보다 작은 쌍의 개수를 구하는 문제이다.

 

얼마전에 xor공부를 하면서 풀게 되었다.

우선 $a$의 배열 원소들을 이진수로 바꿔 트라이에 넣는다.

그리고 $b$의 원소들을 하나씩 뽑아 트라이에서 다음 쿼리를 진행한다.

$a_i, b_i, k_i$는 각각 원소들을 이진수로 바꿨을 때 자릿수

 

* Case 1) $k_i = 1$

$b_i$와 xor한 값이 0이 되도록 하는 값이 트라이의 자식으로 있다면 해당 자식의 수를 더한다.

예를 들어 $b_i=1$이면 트라이의 0번째 자식노드가 있는지 확인한다. (이 경우 언제나 $a \oplus b<k$이다.)

 

$b_i$와 xor한 값이 1이 되도록 하는 값이 트라이의 자식으로 있다면 다음 자릿수로 이동하여 쿼리를 실행한다.

 

* Case 2) $k_i = 0$

$b_i$와 xor한 값이 0이 되도록 하는 값이 트라이의 자식으로 있다면 다음 자릿수로 이동하여 쿼리를 실행한다.

 

$b_i$와 xor한 값이 1이 되도록 하는 값이 있어도 더 진행하지 않는다. (언제나 $a \oplus b > k$가 되기 때문)

시간복잡도는 배열 $b$의 길이를 $N$이라 하고 $a, b$의 원소, $k$ 중 최댓값을 $M$이라 하면 $O(N log M)$이 된다.