2024.04.22. ~ 2024.04.28.

백준 5문제.

 

1. BOJ 31713 : Double Up - S4 

Math + Ad hoc + Hash map 문제.

 

a가 홀수라면, 2^k * a 형태로 나타낼 수 있는 모든 수들끼리는 같은 수로 만들 수가 있다.

이를 활용해서 모든 수를 2로 나눌 수 있을 만큼 나눈다음 같은 수들끼리 묶어보면 가장 많이 등장하는 수의 최대 등장 횟수를 알 수 있다.

 

2. BOJ 3644 : 그래프 매칭 - G3

DP 문제.

 

n = 3, 4, 5, 6일 때의 경우의 수를 보니 C_n = C_n-1 + C_n-2로 피보나치 점화식 형태로 표현됨을 파악했다.

그래서 그대로 대입해보니 정답이 나왔다;;;

 

나중에 알아보니 이렇게 초항이 0,1이 아닌 수에서 피보나치 점화식 형태로 표현되는 수열을 뤼카 수열이라고 한다 하더라. 

문제는 나쁘진 않았는데 다만 수 전체를 출력하지 않고 10^9+7로 나눈 나머지를 구하던지로 바꿨다면 더 좋은 문제였을 것 같다.

 

3. BOJ 2560 : 짚신벌레 - G3

DP 문제.

 

i번째 날에 태어나는 짚신벌레의 수는 i번째 날에 태어난지 a번째 날이 되는 짚신벌레의 수부터 b-1번째 날이 되는 짚신벌레의 수들의 합이 된다. 그래서 dp[0] = 1로 초기화 하고 dp[i] = dp[i-a] + ... + dp[i-b+1] 이렇게 점화식을 세워서 풀면 되는데, dp[i-a] + ... + dp[i-b+1]은 Sliding Window 테크닉으로 계속 갱신하면서 풀어도 되고... 아니면 걍 오버킬로 Segment Tree로 풀어도 된다. 

 

총 시간복잡도는 O(N). (Segment Tree는 O(NlogN)) 재밌는 DP 문제.

 

4. BOJ 20365 : 블로그2 - S3

Greedy 문제.

 

사실상 R이나 B중 하나는 그냥 한 번으로 모든 색깔로 칠할 수 있다.

이후에는 나머지 색깔은 연속된 구간의 개수 만큼 꼭 칠해야 하니 연속된 구간들의 개수들을 세어 풀면 된다.

 

5. BOJ 31422 : AND, OR, XOR 2 - G1

Bitmasking, Combinatorics, Prefix Sum 문제.

 

AND, OR, XOR는 각 비트별로 독립적으로 계산되므로 비트별로 따로따로 계산해서 이를 합쳐도 무관하다. 각각 비트별로 따로 보면 아래와 같이 생각할 수 있다.

 

특정 구간의 AND의 결과로 i번째 비트가 켜졌다면 해당 구간에서의 i번째 비트는 모두 1이어야 한다. 따라서, j번째 원소의 i번째 비트가 1이라면 연속된 구간의 길이를 찾아서 [...j]의 구간 AND결과가 i번째 비트에 1이 들어오는 구간들의 개수를 찾을 수 있다.

 

OR 같은 경우는 특정 구간에 1이 하나만 있으면 되므로 j번째 원소를 포함해서 0이 연속되는 구간을 빼고 나머지 경우의 수들을 전부 더해주면 된다. 따라서 j번째 원소를 포함해 1이 마지막으로 언제 나왔는지를 기록한다면 [...j]의 구간 OR 결과가 i번째 비트가 1인 경우의 수들을 모두 구해줄 수 있다.

 

XOR 같은 경우는 구간의 i번째 비트가 홀수 만큼 켜져있다면 1이 되므로 Prefix Sum을 활용해서 [...j]의 구간 XOR의 결과로 i번째 비트가 1인 경우의 수들을 모두 구해줄 수 있다. [1..j]의 i번째 비트가 홀수 개수만큼 켜져있다면 짝수 개수만큼 켜지는 구간들의 개수를 빼면 경우의 수가 나오고, 역으로 짝수 개수만큼 켜져있다면 홀수 개수만큼 켜지는 구간들의 개수를 빼면 경우의 수들이 나온다.

 

이번 주에 풀었을 때 제일 뿌듯했던 문제. 아직 폼이 아에 뒤진건 아닌것 같아 다행이다.

 

이번 주 일지는 여기서 끝.