138475. 억억단을 외우자 / c++ / level3 / 15분
문제 및 코드
접근 방식
Dynamic Programming
- 하나의 e(nd)와 여러개의 s(tart)가 주어졌을 때, s ~ e의 범위 안에서
가장 많이 등장하는 억억단의 결과값 중 가장 작은 값의 출력
- e의 최대값은 5’000’000 이므로 이는 1 * 5’000’000 와 5’000’000 * 1 의 결과값이다.
- 1 * 1부터 5’000’000 * 5’000’000 의 결과값 중 5’000’000 보다 작은 수의 출현 횟수를 체크한다.
- e ~ e 까지는 e가 가장 많이 등장한다.
- i ~ e의 범위에서 가장 많이 등장한 값 중 가장 작은 값이 dp[i]라고 했을 때,
만약 현재 count[i] 가 count[dp[i+1]] 보다 크거나 같다면(최다값 중 최소값이므로) dp[i] = i 이다. 그렇지 않다면 dp[i] = dp[i+1] 이다.
생각해 볼 점
- 먼저 시간 초과와 메모리 초과를 생각해보고, 허용 범위라고 생각해서 count를 처음에 다 계산하도록 했다.
- 하지만 최대값이 e이므로 1 * 1 부터 e * e 까지 중 e를 넘지 않는 결과값 범위까지 계산했다면 시간을 더 줄일 수 있다.
- 실제로 그렇게 해보니 평균값이 300ms 였던 코드가 평균 33ms정도로 줄었다.
