백준 월간 향유회 2025. 01.

백준 월간 향유회 2025. 01. 대회 문제들이 올라와서 풀어봤습니다.

문제들이 제 기준 쉽지 않았기 때문에 실제 대회에 참가했다면 최대 2 솔이었을 것 같습니다.

마지막 문제인 XOR 머신은 제 역량으로는 도저히 못 푸는 문제인 것 같아 나중에 고수님들의 해설을 보고 풀어야 할 것 같습니다.

 

백준 33272번 TAIDADA

• 이 문제의 핵심은 `어떤 수 x를 골랐을 때, x와 x ⊕ K 두 수는 동시에 고를 수 없다`는 점
• 이를 그래프로 해석하면, 정점이 1부터 M인 그래프에서 x와 (x ⊕ K)를 간선으로 연결한다고 할 때 인접 정점을 동시에 고를 수 없는 집합을 찾는 문제

 

 

백준 33273번 multiple sequence

이차원 dp를 사용하는 문제였고 알고리즘은 다음과 같습니다.

• x_i 기준으로 오름차순 정렬
• 배수 관계 인접 리스트 구성
  • 인덱스가 i < j이고 x_j % x_i == 0일 경우 nxt[i]에 j를 추가

 

• dp[i][k]를 `x[i]를 첫 원소로 하여 정확히 k개의 원소로 구성된 수열을 만들었을 때 얻을 수 있는 최대 합`이라고 정의
  
  • bestNextArr[i][k]는 `i에서 갈 수 있는 모든 j` 중 dp[j][k]의 최댓값을 저장해 둔 배열
  • dp[i][k]는 `i보다 큰 인덱스들 j`에 대한 dp[j][·] 값을 이용해야 하는데, j > i인 것들을 먼저 계산해 두어야 참조할 수 있기 때문에 dp를 채울 때는 i를 큰 인덱스(M - 1)부터 감소하는 순서로 방문
  • i가 정해지면 bestNextArr[i][k]를 구해주고
  • 그다음 dp[i][k]를 채우는데 `x[i]를 k번 연속으로 사용`한 뒤 나머지 k - p개를 nxt[i]에 속한 어떤 j로 이어서 얻을 수 있는 최댓값을 구함 (dp[i][k] = max(x[i] * p + bestNextArr[i][k - p])

 

• 모든 i에 대해 dp[i][N]의 최댓값을 구해주고 해당 값이 NEG_INF일 경우 -1 출력

 

 

백준 33274번 적당한 휴식은 필수

N = 1일 때, N이 짝수일 때 그리고 N이 홀수일 때를 나누어서 접근해야 하는 문제였습니다.

• N = 1일 경우 격자 1 * 1 하나뿐이므로, 그 칸에 0을 넣으면 R1, C1 모두 0이 되므로 mex = 1
• N이 짝수일 때
  • mex = 2 * N을 달성하기 위해 {0, ..., 2 * N - 1} 총 2 * N개를 R과 C에 분배해줘야 함
  • 이를 위해 i가 짝수이면 그 쌍을 R에 분배하고, 홀수이면 C에 분배
  • 그러면 각 부분 집합의 원소 수가 정확히 N이 되고 각 부분 집합의 합도 똑같이 맞춰지며 합집합이 [0, 2 * N - 1]을 전부 포함하므로 mex = 2 * N

 

• N이 홀수일 때
  • mex = 2 * N - 1을 달성하기 위해 {0, ..., 2 * N - 2}와 추가로 0을 한 번 더 넣어 총 2 * N개를 만든 뒤 R과 C에 분배해줘야 함
  • {1, 2, ..., 2 * N - 2}를 서로 다른 두 부분집합으로 정확히 분배하되 각 부분집합 합이 동일하도록 만듦
  • 위와 같이 나눈 두 부분집합 각각에 0을 하나씩 추가로 넣어줌
  • 이렇게 구성하면 합집합은 [0, 2 * N - 2]이며, 2 * N - 1은 빠지게 되므로 mex = 2 * N - 1

 

 

백준 33275번 소소고금

수학적으로 접근해야 하는 어려운 문제였습니다.

부분 문자열이 K 배수인지 판별하는 부분은 ChatGPT의 도움을 받아 겨우 풀 수 있었습니다. (확장형 유클리드 알고리즘 처음 본다... 갓 GPT...)

알고리즘은 다음과 같습니다.

• K를 2^twoCnt * K 형태로 분해
• 부분 문자열이 2로 twoCnt 번 나누어 떨어지면, 끝에서부터 0이 twoCnt개 이상 있어야 함
  • 이에 따라 각 위치에서 연속된 0의 개수 zeroStreak를 구해줌

 

• 주어진 K가 2^n 형태가 아니라면 2^twoCnt * K 형태로 분해된 K는 홀수
  • 왼쪽부터 문자열을 읽으며 지금까지 형성된 이진수를 계속 모듈러로 관리
  • cur에 `지금까지 읽은 이진수를 10진수로 보고 K로 나눈 나머지`를 저장
  • 비트를 하나 더 읽을 때마다 cur = (cur * 2 + (현재비트)) % K
  • 위와 같이 처리하면 언제든지 cur이 0일 때 현재까지 만든 이진수가 K의 배수임을 알 수 있음

 

• 여기서 문제는 부분 문자열 후보가 너무 많다는 것
  
  • 인덱스 범위가 [0, i]까지 읽은 나머지가 cur_i라고 할 때 중간의 j번째 (0 <= j < i)부터 i번째까지 형성된 부분 문자열이 K 배수가 되기 위해서는 (cur_i - cur_j * 2^(i - j)) % K == 0이어야 함
  • 부분 문자열 S_(j+1), ..., S_i의 값을 전체 접두사 Prefix_i에서 앞부분 Prefix_j를 빼는 방식으로 표현할 수 있고 빼야 하는 양은 P_j * 2^(i - j)이기 때문 (이진수에서 앞부분을 왼쪽으로 (i - j)만큼 Shift 한 값)
  • 하지만 위 식을 모든 쌍 [j, i]에 대해 직접 계산하는 것은 비효율적이기 때문에 나머지를 효율적으로 관리하기 위해 2의 역원을 사용하는 방식 채택
    • cur을 구한 다음 2^i에 대한 역원(mod K)을 곱해서 정규화 진행 ex) a = (cur_i * (2^(-i) mod K)) mod K)
    • 이렇게 하면 i번째 위치에서 구한 `정규화된 나머지`가 과거에 어떤 값과 같았을 때 해당 부분과 연결하여 K의 배수 여부를 쉽게 확인 가능
    • 구한 정규화 나머지 a를 `과거에 몇 번 나왔는지` 세어두었다가 같은 a가 반복되면 (i - j) 길이의 부분 문자열이 K의 배수임을 알 수 있게 됨

 

• 답을 구하기 위해 0 ~ N - 1까지 다음 과정을 반복
  • cur = (cur * 2 + (S[i] == '1')) % K
  • 만약 S[i] == '0'이면 zeroStreak++, 아니면 zeroStreak = 0
    • zeroStreak이 증가할 때 twoCnt 관련 처리를 위해 answer에 추가되는 케이스 존재
  • 나머지 a를 구해주고
  • 만약 끝에 0이 충분히 모여 zeroStreak >= twoCnt라면
    • cur == 0이면 전체가 K로 나누어 떨어지기 때문에 answer++
    • 과거에 같은 정규화 나머지였던 패턴 수만큼 더함 (answer += v[a])
  • 큐에 a를 넣고, 부분 문자열 길이가 twocnt에 도달해야 비로소 기록을 시작하기 위해 큐 길이가 twocnt 이상이면 이제부터 “나머지 a'”가 공식적으로 한 번 등장한 것으로 간주하여 가장 오래된 a를 빼서 v[a]++

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~