New Year Chaos c#

문제 요약

1, 2, 3, 4, 5...의 데이터가 담겨있는 int형 배열 q[]

뒤의 숫자는 앞으로 최대 두 칸까지 이동할 수 있다.

 

세 칸 이상 이동 시 : Too chaotic 출력

그 외 : 앞으로 이동한 횟수를 출력

 

 

Too chaotic 출력

각 숫자 i는 i - 1 인덱스에 위치한다.

   숫자 4는, 현재 3인덱스에 위치 ( q[3] = 4)

   숫자 4는 최대 두 칸 앞으로 이동할 수 있으므로

   인덱스 2, 1에 위치할 수 있다. ( q[2] = 4, q[1] = 4 가능)

   인덱스 0에 위치 시 Too chaotic( q[0] = 4인 경우 Too chaotic)

즉 q[i] - 1 - i > 2 일 때 Too chaotic이 출력되도록 한다.

 

 

birbe출력

q[j] > q[i] (j < i) 인 이유

처음 배열 q의 값들은 오름차순으로 정렬되어있어 앞의 값이 뒤의 값보다 작다.

하지만 배열 q의 값들이 앞으로 이동했을 경우 앞의 값이 뒤의 값보다 큰 경우가 발생

따라서 q[0] ~ q[i - 1] 중에서 q[i]의 값보다 큰 값의 개수를 세어 보면 이동한 숫자를 알 수 있다.

 

ex) 현재 q[] = {1, 2, 3, 4, 5}

숫자 4가 앞으로 한 칸 이동 

q[] = {1, 2, 4, 3, 5}

= 숫자 1 앞에 1보다 큰 값 없음

  숫자 2 앞에 2보다 큰 값 없음

  숫자 4 앞에 4보다 큰 값 없음

  숫자 3 앞에 3보다 큰 값은 4 하나

  숫자 5 앞에 5보다 큰 값 없음

= 총 한 번 이동

 

숫자 4가 앞으로 두 칸 이동

q[] = {1, 4, 2, 3, 5}

= 숫자 1 앞에 1보다 큰 값 없음

  숫자 4 앞에 4보다 큰 값 없음

  숫자 2 앞에 2보다 큰 값 4 하나

  숫자 3 앞에 3보다 큰 값은 4 하나

  숫자 5 앞에 5보다 큰 값 없음

= 총 두 번 이동

 

 

Max(0, q[i] - 2)의 이유

앞의 값과 비교할 때 q[0] ~ q[i - 1]까지 계속 비교할 필요가 없음

최대 앞으로 두칸 이동할 수 있기 때문에

q[i] - 2 부터 비교하면 됨

 

ex)

q[i]가 4일 때 4보다 큰 값은 5, 6, 7...이 있음

5는 최대 q[2]까지만, 6은 q[3]까지만 이동 가능

즉, q[2]이부터 q[i - 1]까지 4보다 큰 값의 개수를 찾으면 됨