[백준] 31790. 간단한 문제

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

문제 요약

• 순열 A가 있고, 0 ~ i까지 연속 수열의 원소들을 p로 나누면 나머지가 0 ~ p-1이 나올 것임
• 가장 많이 나온 빈도수를 구할 수 있을 것임 => ${b_i}$
• p와 ${b_i}$ 가 주어지면 이를 만족하는 순열 A가 존재하는지 묻는 문제

접근법

• 문제를 한번에 이해하기는 난해하다.
• 실제를 수열을 구성한다기 보다는 b값만 가지고 고민해볼 것들이 있음
• 천천히 생각해보면 꼭 만족해야하는 조건들이 있다.
  • 앞에 숫자보다 작아질 수 있을까? -> 연속 수열이니까 앞에했던 내용을 포함함 -> 작아질 수가 없다!
  • 앞에 숫자보다 엄청 커질 수 있을까? -> 연속 수열이 하나씩 증가한다 -> 같거나 하나 커지거나
  • 숫자가 엄청 작아질 수 있을까? -> 최대값 말고, 다른 값들이 모두 최대값이라고 했을때 -> 최대값 * p가 i에 못 미친다면?
  • 숫자가 엄청 커질 수 있을까? -> 최대값이 i보다 크다면??
• 여기에 순열이라는 조건도 있음
  • 1 ~ N 각각을 p로 나누면 나머지 빈도수가 나올 것임
  • 빈도수는 아무리 커봐야 상한선이 있음
  • b 값이 상한선을 넘는다면?
• 위 조건을 만족한다면 A를 만들어 낼 수 있음
• 비둘기집 비슷한 논리