BOJ 10610 - 30
규칙을 파악해서 풀어야 하는 그리디 문제다.
N제한이 10의 5승이니, 굉장히 큰 값이 들어올 수도 있다는 것을 알 수 있고, 단순히 그 숫자들을 경우의 수에 맞게 조합해서 찾아내는 방식은 사용할 수 없다.
접근 방법
3의 배수에는 어떤 규칙이 있다.
그 수를 구성하는 숫자를 다 쪼개서 합해봤을 때, 이 수가 3으로 나누어 떨어진다는 것. 예를 들어 981이라는 수가 있으면 9+8+1은 3으로 나누어 떨어진다.
이 규칙을 깨닫고 나면 다음과 같은 방법을 생각해볼 수 있겠다.
- 0부터 9까지 각각 몇 개 들어있는지 count하는 배열 작성
- input값을 char배열이나 다른 방식으로 전처리 해놓고 일일히 확인해서, count배열을 증가해주는 것과 동시에 누적합 구해주기 (이번에 981을 입력 받았으면 9+8+1을 누적합 변수에 넣어주는 식으로)
30의 배수가 되려면 최소 한 개 이상의 0이 존재해야한다.
따라서 count[0]이 0이거나 누적합 % 3이 0이 아닌경우는 아예 30의 배수를 만들 수 없다고 봐도 무방하다.
여기까지 처리를 했으면 적절하게 그리디한 해법으로 답을 구하면 된다. (조금만 생각해보면 최대값이 몇인지 알 수 있음)