본문에 올려주신 코드는 말씀하신 것처럼 N초가 지난 후의 수열을 직접 다 구하는 방식으로 이 문제를 풀기 위해 가능한 접근이 아닙니다. 다음과 같이 접근해야 합니다.
solve(n, k): n초가 지난 후 수열에서 1번째 수부터 k번째 수까지 각 수의 개수와 k번째 문자를 구함
solve(n, k)의 값은 solve(n-1, (k-1)//3+1)을 재귀호출해서 그 결과를 이용하여 구할 수 있습니다.
문제에서 요구하는 답은 solve(N, R) - solve(N, L-1)과 같은 형식을 가집니다.
gwanwoo3849 1년 전
이 문제는 풀이법이 바텀업밖에 생각이 안 나는데 분할정복을 어떻게 적용할까요...? 저는 탑다운에서 밖에 적용을 안 해봐서 생각이 잘 안 나네요...ㅜㅜ 일단 단순재귀로 하면 3^20이라 무조건 시간초과가 날 거고... 힌트라도 주실 분 ㅜㅜ