https://www.acmicpc.net/problem/22952
문제요약
- 순열이 있고, 새로운 순열을 정의함
- 새로운 순열은 원래수열의 i번째까지의 합 mod N
- 새로운 순열에서 서로 다른 값이 2N+1이 되도록
접근법
- 문제 티어는 낮지만(실버) 아이디어가 쉽진 않았음
- 전체 합은 정해져있기때문에 마지막 값은 정해져 있으므로 처음 값은 그 값으로 하고......그리디처럼 해야하나 했는데 어려웠음
- 두개씩 짝 지으면 n이 되는 수들이 있음 : 처음과 끝, 두번째와 끝에서 두번째..
- 더하면 n이니까 나머지 연산에 활용할 수 있지 않을까 생각함
- a 가 나온 상태에서 n을 더하고 나머지 연산을 하면 또 a가 나오므로 나타나는 숫자의 종류를 줄일 수 있을 것 같음
- 숫자의 종류가 절반보다큰값 이하이므로 이용하면 뭔가 될 것 같음