8/22 Problem Solving

2825 수업시간에 교수님 몰래 교실을 나간 상근이 (G2)

 

비트 마스크로 0~9 사이의 숫자가 포함되어 있는지 여부를 상태로 표현해서 세준다. 쌍의 개수를 세줄 때 자기자신끼리의 쌍과 중복되는 쌍은 제거해야한다.

 

http://boj.kr/065bfe2aa12a4a85abb60aed0ed3d74a

 

 

17497 계산기 (G2)

 

처음에는 BFS로 생각했는데 경우의 수가 최대 4^99가 되서 불가능하다. 연산이 전부 2와 연관이 있는것에 주목하자. 2를 더하는 것은 1번째 비트에 1를 추가하는 것과 같고 빼는 것도 마찬가지이다. 곱하기는 left shift, 나누기는 right shift와 같다. 우리가 구해야 하는 것은 0에서 N까지 가는 방법인데 N에서 0으로 만드는 방법을 생각해보자.

 

1. 0번째 비트에 1이 있다면 (...1) left shift를 해야한다. 0번째 비트를 건드는 방법은 없기 때문이다. 일단 1번째 비트로 1을 밀고서 다음 연산을 해야한다.

2. 1번째 비트에 1이 있다면 (...10) 뺄셈을 해줘야 한다. 덧셈의 경우 carry가 발생해서 다시 앞에 영향을 주기 때문에 선택지에서 배제한다.

3. 위 두가지 경우가 아니라면 (...00) right shift로 밀어서 0을 제거해준다.

 

역순으로 연산을 하므로 실제 답을 구할때는 해당 연산의 반대 연산을 저장해서 뒤집어야한다.

 

http://boj.kr/414591f76c10404b9e54c0349946bd5f

 

 

2696 중앙값 구하기 (G2)

 

priority queue 두개를 두고 중앙값들을 관리한다. 중앙값 기준 왼쪽은 max heap, 오른쪽은 min heap으로 두고 각각 top들을 비교해서 현재 보고 있는 원소를 어디쪽에 넣어줄지 결정해준다. 두 heap의 크기 차이가 1를 넘지 않도록 유지한다.

 

http://boj.kr/25bda76a19ca4c899b64a8c44ac0a32a

 

 

11524 Immortal Porpoises (G2)

 

N번째 피보나치 수를 구해야 되는데 N이 최대 2^48이다. 피보나치 수를 구하는 점화식을 행렬의 거듭제곱으로 표현할 수 있다. 그러면 빠른 거듭제곱을 이용해서 쿼리마다 피보나치 수를 구하는 작업을 O(logN)으로 줄일 수 있다.

 

 

http://boj.kr/067d9360831747b5a3418670b445ef6d

 

 

17180 문자열 비교하기 (G2)

 

d[i][j] = 문자열 a의 처음 i개 문자와 문자열 b의 처음 j개 문자 간의 최소 차이

d[i][j] = min(d[i-1][j-1]+abs(a[i]-b[j]),d[i-1][j]+abs(a[i-1]-b[j]),d[i][j-1]+abs(a[i]-b[j-1]))

 

두 문자열에서 문자를 늘리지 않고 쓴 것, a에서 문자를 늘린 것, b에서 문자를 늘린 것 중에 최소값을 채우면 된다.

 

http://boj.kr/616268bc18a14f58b811bdd05f61e145