백준 Hello, AlKon! 2025

백준 33701번 새천년관

• 단순 구현 문제

 

 

백준 33702번 비밀번호

• DFS와 비트마스크를 결합한 백트래킹으로 그래프 상의 모든 해밀토니안 경로를 세는 문제

 

 

 

백준 33703번 건덕이의 돌탑

• 하노이 탑 이동 문제와 달리 `중간에 있는 돌도 한 번에 꺼낼 수 있다`는 제약 완화 덕분에
  • 어떤 방석에서 가장 큰 돌을 제외한 모든 돌은 언제든지 단 한 번의 이동으로 꺼낼 수 있고
  • 꺼낸 돌을 놓을 때에도 빈 방석 또는 더 큰 돌이 있는 방석 위에만 놓으면 되므로 그 방석 내 정렬이 자동으로 보장됨

 

• 위 두 가지를 이용하면, 개별 돌 하나를 세 번째 방석에 놓기까지 필요한 이동 횟수를 돌 크기별로 합산하는 방식으로 해를 구할 수 있음
  • 맨 밑의 돌이 아니라면 한 번에 꺼낼 수 있으므로, 돌 k를 꺼내는 데는 그 위에 있는 더 작은 돌  k−1개를 미리 제거해야 하고, 각 제거는 1회 이동 (k - 1)
  • 실제로 돌 k 자체를 세 번째 방석 위에 놓는 행위가 1회 이동 추가
  • 정리하면 1 + ... + N이므로 답은 N * (N + 1) / 2

 

 

 

백준 33704번 안정적인 구간

• ⌈K/2⌉번째 원소와 정렬 후의 ⌈K/2⌉번째 원소가 같으면 조건을 만족
  • K=2인 경우, ⌈2/2⌉=1이므로 부분 배열의 첫 번째 원소가 두 수 중 작은 값이어야 함
    • 즉, 인접 쌍 A_i ​<= A_(i+1)가 성립하면 됨
  • K=3인 경우, ⌈3/2⌉=2이므로 가운데 원소가 세 수의 중간값이면 됨
  • 배열 길이가 3 이상이면 위 두 조건 중 하나가 항상 성립하므로 항상 문제에서 요구하는 부분 배열이 반드시 존재함

 

• 정리하면
  • N >= 3인 경우 항상 YES
  • N = 2인 경우  A[0] <= A[1]인지 확인 필요

 

 

백준 33705번 마스코트 정하기

• 문제를 요약하면 투표장에 남길 학생 위치들의 집합 K를 정하고, 나머지 구간들을 연속 구간으로 몇 번 제거해야 하는지 구하는 문제
  • 전체 학생을 그대로 둘 때 1번 후보가 과반을 얻는지 확인
  • 한 번의 연속 구간 제거로 1번 후보가 과반을 얻는지 확인
    • 뒤쪽을 모두 내쫓고 앞쪽만 남기는 경우
    • 앞쪽을 모두 내쫓고 뒤쪽만 남기는 경우를 각각 검사
  • 위 두 경우 모두 만족하지 못하면 행동 횟수는 2

 

 

백준 33706번 오름차순 최단 경로

• `i=2…N에 대해 i보다 작은 레이블의 이웃이 존재하는가`를 확인하는 문제

 

 

 

백준 33707번 젓가락으로 메추리알 집기

• 흑백 체스판처럼 두 칸이 인접하면 서로 다른 색이 된다는 점에 착안하여, 한쪽 색깔에 속하는 칸만 모두 탐색하는 전략을 사용
• 격자의 모든 칸을 두 가지 색으로 나누었을 때, 둘 중 더 작은 쪽 색깔의 칸 수는 ⌊NM/2⌋ 이하가 됩
• 탐색 과정에서 
  • 젓가락질한 칸에 메추리알이 있다면 즉시 1을 받아 프로그램 종료
  • 메추리알이 없다면, 칸과 인접한 위치에 있던 메추리알만 움직이는데, 한 쪽 색깔만 탐색 전략에서는 현재 탐색 중인 칸과 같은 색의 칸들은 서로 인접하지 않으므로, 메추리알이 이미 지나간 칸으로 돌아가지 않고 아직 남아 있는 칸으로만 이동
  • 결국 메추리알은 한 번도 탐색하지 않은 같은 색의 칸 위에 있게 되고, 그 칸을 젓가락질할 때 반드시 잡히게 됨

 

 

 

백준 33708번 인수분해 정렬

• 쿠가 할 수 있는 연산은 인접 두 수의 곱을 보존하면서 두 수의 합은 반드시 바꾸는 것
  • 전체 수열의 곱은 연산 전후에 변하지 않음
  • 바꿔쓸 수 있는 인접 쌍 (A_i​,A_i+1​) 은 곱이 1이거나 소수가 아닐 때에만 존재
    • 곱이 1이면 (1, 1)로만 분해되고 합은 항상 2
    • 곱이 소수이면 (1, 소수) 혹은 (소수, 1)로만 분해되고 합은 항상 같음
    • 반면 곱이 합성수일 경우 합을 변경할 수 있음

 

• 따라서 `연산을 전혀 할 수 없는` 수열은 인접 모든 쌍의 곱이 1이거나 소수인 경우뿐이며, 이때 수열을 바꿀 수 없으므로 초깃값이 이미 비내림차순이 아니면 답은 NO
• 이미 비내림차순이면 아무 연산 안 해도 YES.
• 그렇지 않지만 인접에 한 쌍이라도 합성수인 곱이 있으면( 충분한 횟수의 연산으로 전체 수열을 비내림차순으로 만들 수 있음

 

 

개발환경:Visual Studio 2022

 

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