[백준] 22952. permutation making

newbieski·2021년 11월 20일
0

백준

목록 보기
45/210

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

문제요약

  • 순열이 있고, 새로운 순열을 정의함
  • 새로운 순열은 원래수열의 i번째까지의 합 mod N
  • 새로운 순열에서 서로 다른 값이 N2+1{{N \over 2} + 1 }이 되도록

접근법

  • 문제 티어는 낮지만(실버) 아이디어가 쉽진 않았음
  • 전체 합은 정해져있기때문에 마지막 값은 정해져 있으므로 처음 값은 그 값으로 하고......그리디처럼 해야하나 했는데 어려웠음
  • 두개씩 짝 지으면 n이 되는 수들이 있음 : 처음과 끝, 두번째와 끝에서 두번째..
  • 더하면 n이니까 나머지 연산에 활용할 수 있지 않을까 생각함
    • a 가 나온 상태에서 n을 더하고 나머지 연산을 하면 또 a가 나오므로 나타나는 숫자의 종류를 줄일 수 있을 것 같음
    • 숫자의 종류가 절반보다큰값 이하이므로 이용하면 뭔가 될 것 같음
profile
newbieski

0개의 댓글