[백준] 31873. 별 수호자 룰루

https://www.acmicpc.net/problem/31873

문제 요약

• 1,2,3,...,N(N=100만)
• N의 약수 K
• K개씩 그룹으로 묶었을때, 그룹의 합이 K로 나누어 떨어지지 않도록 구성할 수 있을까?

접근법

• 숫자들을 K의 나머지로 표현하면 1,2,3,...K-1,0,1,2,3,... 이런 패턴으로 나타남
• K가 짝수이면?
  • 순서대로 K개씩 그룹을 만들면 항상 성공
  • K가 4면, 1 2 3 0, 1 2 3 0, ... 이런식이니까
  • 수식으로 표현하면 K * (K-1)/2 에서 (K/2) * (K-1)이 되어서 K의 배수가 안됨
• K가 홀수이면?
  • N==K이면 안됨 : K * (K+1)/2 = K의 배수
  • K==1이어도 안됨
  • 그 외에는 조작을 해본다!
• 조작1
  • 숫자들을 그룹지어 나열해본다
  • 1 2 3,...,K-1,0 => K의 배수(K*(K-1)/2)
  • 1 2 3,...,K-1,0 => K의 배수(K*(K-1)/2)
  • 첫번째 숫자와 두번째 숫자를 바꾸면
  • 2 2 3, ..., K-1,0 => 아까보다 +1
  • 1 1 3, ..., K-1,0 => 아까보다 -1
  • 그럼 그룹의 나머지가 (0,0,0,0,...) => (+1,-1,+1,-1)이 된다.
• 조작2
  • 조작1에서 교환이 딱 안떨어지면? 즉 그룹의 개수가 홀수이면?
  • (+1, -1, +1, -1, 0) 이되면 마지막 그룹은 어떻게??
  • 마지막 그룹과, 마지막 이전 그룹과 교환을 함
  • (+1, -1, +1, -2, +1) 이 되도록
  • 마지막 그룹에서 나머지가 0인것과, 이전 그룹에서 나머지가 1인 것을 교환
• 결론
  • 홀/짝 판단 => 짝 인경우 항상 성공
  • 홀인 경우 안되는 경우 판단
  • 두 개 그룹씩 나머지가 1인것, 나머지가 2인것을 맞교환 함
  • 짝이 안지어진 끝 그룹이 있으면 끝 그룹에서 나머지가 0인것과 끝 전 그룹에서 나머지가 1인것을 맞교환함