PS | 0814~0820 | 2022

0816부터 시작

클래스 5

클래스 5 안 푼 문제 중에 귀찮은 문제들이 많다

 

9328 열쇠

흔한 비트마스크 bfs 문제인줄 알았는데 열쇠 개수가 100개

문을 만나면 열쇠가 있는 경우 바로 큐에 삽입하고, 없다면 문 리스트에 삽입한다.

bfs를 돌리는데 열쇠 하나를 새로 얻으면 지금까지 봤던 문 리스트에 있던 문들을 큐에 삽입한다.

맵 테두리를 0으로 감싸주면 single source bfs가 가능해서 구현이 훨~씬 편하다.

랜디

0816

• A - 물병
• B - 고층 건물
• C - 방 번호
• D - 롤러코스터
• E - 큐빙
• F - 스타 대결

A: 이진법으로 나타냈을 때 비트의 개수가 K개 이하인 N 이상의 최소 자연수를 구하면 됩니다. N이 작아서 __buitlin_popcount(X)로 반복문 돌려줘도 되고, 
가장 작은 비트부터 차례대로 올라가는 방법도 있습니다.
https://www.acmicpc.net/source/share/58c11b1666f0455ca7af4a3c887e9d92

B: 브루트 포싱하면 됩니다. 비교할 때 long long 써야 돼요
https://www.acmicpc.net/source/share/af17b6b2f77e46038d997229ae6f2088

C: dp[i] i원까지 써서 가능한 최대 수(문자열)로 정의하고 O(M^2 * 문자열 길이)로 dp 채워주면 됩니다.
https://www.acmicpc.net/source/share/10583dc5f35343838cdfe5a0e9007baa
D: n과 m 중 홀수가 하나라도 있는 경우는 모든 칸을 방문할 수 있습니다.
둘다 짝수 인 경우,
체스판 형태로 칠했을 때 
시작점이랑 색깔이 다른 경우 1개를 빼고는 다 방문 가능,
시작점이랑 색깔이 같은 경우 1개(무조건 다른 점도 방문 못함)만 빼고 방문하는건 불가능이므로 시작점이랑 색깔이 다른 경우 중 최솟값을 찾아내서 그것만을 안 지나는 경로를 출력해주면 됩니다.

구현이 너무 어려워서 저는 8X8 배열을 종이에 그리고 가운데 쪽에 있는 칸을 제외하는 방식으로 시뮬 해봤어요.
https://www.acmicpc.net/source/share/13d5378b71dd4eba8ee2413ef3f2bf39

E: 구현 ㅠㅠ
https://www.acmicpc.net/source/share/c41964df325c4426b53f5963191db2ec
F: 플로우 같은데 전 플로우를 아직 몰라요. 조만간 공부하겠습니다.

 

0817

• A - 중앙값 제거
• B - 사자와 토끼
• C - YouTube
• D - 1-Trees and Queries
• E - 도미노 (Large)
• F - 강강술래
• G - XorSum   

G 생각의 흐름대로 풀이 적어볼게요.
G:  https://www.acmicpc.net/problem/15896 와 비슷한 방법을 사용한다.
i번째 비트가 켜져 있는지 판정하기 위해서 각 원소에 두가지를 저장해놓자.
수열의 원소를 k라 할 때
i번째 비트가 켜져 있는지  = bool( k & (1<<i) )
i번째 비트 앞에 있는 수(나머지) = k & ( (1<<i) - 1 )

이제 이 나머지들을 i번째 비트가 켜져 있는 것들과 꺼져 있는 것들로 분리하면
REM (i, 0/1) :  i번째 비트가 꺼진/켜진 수들의 나머지들을 저장하는 벡터
를 얻을 수 있다.

예제가 
4
3 9 6 6인데
여기서 i = 2의 경우를 생각해보면
1<<i = 4
REM(2,0) :  3, 1
REM(2,1) : 2, 2
각 둘다 정렬해보자.
(1,3)
(2,2)가 된다.

이 벡터가 있을 때 좋은 점은 빠르게 스위핑할 수 있다는건데
예를 들어 REM(2,0) 에 있는 수들과 REM(2,1)에 있는 수들을 더했을 때
2번째 비트끼리 더한 것은 1이되고 아래 있는 나머지들을 더했을 때
받아올림이 일어나지 않는 경우에만 실제로 정답에 1<<i가 xor되게 된다.
(2,2)가 정렬되어 있다고 생각하면
각 원소에 대해 이분탐색 등으로 2와 더했을 때 4보다 작은 경우의 개수를 빠르게 구할 수 있다. 다른 경우도 비슷하게 하면 된다.

1<=i<=j<=n에 대해 구하는것이므로 i=j인 경우는 따로 처리해주고
i<j인 경우만 처리해주는게 살짝 고민이 필요한데 잘 생각해보면 REM 배열에서 자기보다 작거나 같은(같을 경우 자기보다 앞에 있는) 수의 개수를 세는 것으로 해결 가능

여기까지 하면 8%에서 시간초과가 나는데

이분탐색 -> 투포인터
REM 배열 정렬 -> REM(i-1)을 이용해 REM(i)를 만드는 병합정렬
로 바꿔주면 AC가 나옵니다

시간복잡도: O(31N)
http://boj.kr/cad29f78545a4a96977a09a5a4f0d3fe  

UPD: 병합정렬보다 2진법에서의 라딕스 소트에 가깝다.