[백준 13144] List of Unique Numbers

[ 백준 13144 : List of Unique Numbers ]

구현문제! 라기엔 조금 생각이 필요했다.

우선 배열크기 n이 10만이고 연속된 수를 찾으면 최악에 10만번 탐색해야되서
완전 탐색으로 찾으면 안된다.

나는 문제를 볼 때 완탐이 되는지 안되는지를 먼저 보는데 완탐이 불가능하다면
내가 아는 알고리즘을 생각해보고 그 안에서 이뤄지지 않는다면
규칙이 있는지 혹은 계산으로 되는지를 생각한다.
이문제는 계산이 가능했다!

내가 생각한 방법으로는 인덱스를 저장하는 방법이었다.

10
1 2 3 4 5 6 7 6 3 1
이라는 입력이 주어진다고 생각하자.

0번 인덱스에서 만들 수 있는 수열은 몇 개일까?
{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6},{1,2,3,4,5,6,7} 이렇게 총 7개가 존재한다.
1번 인덱스는?
{2}~~{2,3,4,5,6,7} 6개.
그다음은 5개

규칙을 찾았다!!

for문을 돈다고 생각해보면
0 에서는 아직 첫 번째 인덱스배열에 미치지 못한다. 7-0
1,2,3,4,5 도 마찬가지 7-1, 7-2, 7-3, 7-4, 7-5
6번 인덱스는 이제 넘어버렸다.
이럴때 인덱스 배열의 비교할 부분을 한 칸 높여준다. {2,8}과 비교를하는데
마찬가지로 인덱스 시작부분이 6 을 넘지 못하므로 인덱스 배열 3과 비교를한다.
그래도 안되므로 이제 n에서 빼주기 시작한다.
10-6, 10-7 10-8, 10-9

이제 이 숫자들을 다 더해주면 답이나온다..

설명이 알아듣기 좀 힘들것 같은데 소스로 보면 이해가 될 수도 있당.